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

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

### Scatter

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

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