Sparse Arrays: Manipulating Lists

Lists are normally specified in the Wolfram Language just by giving explicit lists of their elements. But particularly in working with large arrays, it is often useful instead to be able to say what the values of elements are only at certain positions, with all other elements taken to have a default value, usually zero. You can do this in the Wolfram System using (RefLink[SparseArray, paclet:ref/SparseArray]) objects.

Ordinary lists and sparse arrays.

This specifies a sparse array:

SparseArray[{2->a,5->b}]

Here it is as an ordinary list:

Normal[%]

This specifies a two-dimensional sparse array:

SparseArray[{{1,2}->a,{3,2}->b,{3,3}->c}]

Here it is an ordinary list of lists:

Normal[%]

Creating and converting sparse arrays.

This generates a sparse array version of a list:

SparseArray[{a,b,c,d}]

This converts back to an ordinary list:

Normal[%]

This makes a length 7 sparse array with default value x:

SparseArray[{3->a,5->b},7,x]

Here is the corresponding ordinary list:

Normal[%]

This shows the rules used in the sparse array:

ArrayRules[%%]

This creates a banded matrix:

SparseArray[{Band[{1,1}]->x,Band[{2,1}]->y},{5,5}]//MatrixForm

An important feature of (RefLink[SparseArray, paclet:ref/SparseArray]) is that the positions you specify can be patterns.

This specifies a 4×4 sparse array with 1 at every position matching {i_,i_}:

SparseArray[{i_,i_}->1,{4,4}]

The result is a 4×4 identity matrix:

Normal[%]

Here is an identity matrix with an extra element:

Normal[SparseArray[{{1,3}->a,{i_,i_}->1},{4,4}]]

This makes the whole third column be a:

Normal[SparseArray[{{_,3}->a,{i_,i_}->1},{4,4}]]

You can think of (RefLink[SparseArray, paclet:ref/SparseArray])[rules] as taking all possible position specifications, then applying rules to determine values in each case. As usual, rules given earlier in the list will be tried first.

This generates a random diagonal matrix:

Normal[SparseArray[{{i_,i_}:>RandomReal[]},{3,3}]]

You can have rules where values depend on indices:

Normal[SparseArray[i_->i^2,10]]

This fills in even-numbered positions with p:

Normal[SparseArray[{_?EvenQ->p,i_->i^2},10]]

You can use patterns involving alternatives:

Normal[SparseArray[{1|3,2|4}->a,{4,4}]]

You can also give conditions on patterns:

Normal[SparseArray[i_/;3<i<7->p,10]]

This makes a band-diagonal matrix:

Normal[SparseArray[{{i_,j_}/;Abs[i-j]<2->i+j},{5,5}]]

Here is another way:

Normal[SparseArray[{Band[{1,1}]->{2,4,6,8,10},Band[{1,2}]->{3,5,7,9},Band[{2,1}]->{3,5,7,9}},{5,5}]]

For many purposes, the Wolfram System treats (RefLink[SparseArray, paclet:ref/SparseArray]) objects just like the ordinary lists to which they correspond. Thus, for example, if you ask for parts of a sparse array object, the Wolfram System will operate as if you had asked for parts in the corresponding ordinary list.

This generates a sparse array object:

s=SparseArray[{2->a,4->b,5->c},10]

Here is the corresponding ordinary list:

Normal[s]

Parts of the sparse array are just like parts of the corresponding ordinary list:

s[[2]]

This part has the default value 0:

s[[3]]

Many operations treat (RefLink[SparseArray, paclet:ref/SparseArray]) objects just like ordinary lists. When possible, they give sparse arrays as results.

This gives a sparse array:

3 s+x

Here is the corresponding ordinary list:

Normal[%]

(RefLink[Dot, paclet:ref/Dot]) works directly with sparse array objects:

s.s

You can mix sparse arrays and ordinary lists:

s.Range[10]

The Wolfram System represents sparse arrays as expressions with head (RefLink[SparseArray, paclet:ref/SparseArray]). Whenever a sparse array is evaluated, it is automatically converted to an optimized standard form with structure (RefLink[SparseArray, paclet:ref/SparseArray])[(RefLink[Automatic, paclet:ref/Automatic]),dims,val,…].

This structure is, however, rarely evident, since even operations like (RefLink[Length, paclet:ref/Length]) are set up to give results for the corresponding ordinary list, not for the raw (RefLink[SparseArray, paclet:ref/SparseArray]) expression structure.

This generates a sparse array:

t=SparseArray[{1->a,5->b},10]

Here is the underlying optimized expression structure:

InputForm[%]

(RefLink[Length, paclet:ref/Length]) gives the length of the corresponding ordinary list:

Length[t]

(RefLink[Map, paclet:ref/Map]) also operates on individual values:

Normal[Map[f,t]]