# Gather-scatter (vector addressing)

Gather-scatter is a type of memory addressing that often arises when addressing vectors in sparse linear algebra operations. It is the vector-equivalent of register indirect addressing, with gather involving indexed reads and scatter indexed writes. Vector processors (and some SIMD units in CPUs) have hardware support for gather-scatter operations, providing instructions such as Load Vector Indexed for gather and Store Vector Indexed for scatter.

## Definitions

### Gather

A sparsely-populated vector $y$ holding $N$ non-empty elements can be represented by two densely-populated vectors of length $N$ ; $x$ containing the non-empty elements of $y$ , and $idx$ giving the index in $y$ where $x$ 's element is located. The gather of $y$ into $x$ , denoted $x\leftarrow y|_{x}$ , assigns $x(i)=y(idx(i))$ with $idx$ having already been calculated. A C implementation is

```for (i=0; i<N; ++i)
x[i] = y[idx[i]];
```

### Scatter

The sparse scatter, denoted $y|_{x}\leftarrow x$ is the reverse operation. It copies the values of $x$ into the corresponding locations in the sparsely-populated vector $y$ , i.e. $y(idx(i))=x(i)$ .

```for (i=0; i<N; ++i)
y[idx[i]] = x[i];
```