Working with Sparse Arrays

Basic Operations

A SparseArray object can be created by giving a list of those elements that are nonzero. In[1]:= Out[1]=

By default, a sparse matrix will print with a special output format. You can see the matrix that the sparse array represents by using MatrixForm. In[2]:= Out[2]//MatrixForm=

Operations on sparse matrices are all equivalent to the operations on dense matrices. For example, arithmetic is supported and a sparse array is the result. In[3]:= Out[3]= In[4]:= Out[4]//MatrixForm=

Listable operations also work on sparse arrays to thread over all elements. In[5]:= Out[5]= In[6]:= Out[6]//MatrixForm=

All combinations of matrix multiplication using the function Dot are supported. This demonstrates the dot product of two sparse arrays. In[7]:= Out[7]= In[8]:= Out[8]//MatrixForm=

This demonstrates the dot product of a sparse array with a dense vector. In[9]:= Out[9]=

The dot product of a sparse array with a dense matrix is supported. In[10]:= Out[10]=

Sparse representations are useful because they do not store every element. If one particular value, typically this is zero, appears many times in the sparse array, it can be much more efficient if only elements that are different from this common value are stored. The default output format shows the number of nondefault elements and the dimensions. In[11]:= Out[11]=

If a single number is added to the sparse array, it is added to all elements and also to the default element, which was zero. Now that the default element is no longer zero but 1.5, it is shown in the output. In[12]:= Out[12]=

If the N command is applied to a sparse matrix, it works on all the elements. This builds an example 3×3 sparse matrix. In[13]:= Out[14]//MatrixForm=

When N is applied to the sparse matrix, the result is a sparse matrix with elements (including the default element) that are all approximate machine numbers. In[15]:= Out[15]//MatrixForm=

Here N with a precision argument is applied to the matrix. This generates a sparse matrix of approximate real numbers with 20 digits of precision. Note that N[0, 20] is still 0. In[16]:= Out[16]//MatrixForm=

SparseArray

The main function for generating a sparse array is SparseArray. This can operate on a matrix to generate its sparse representation. In[1]:= Out[2]= In[3]:= Out[3]//MatrixForm=

SparseArray can also take a list of rules showing the values for certain parts. In[4]:= Out[4]= In[5]:= Out[5]//MatrixForm=

An equivalent syntax for SparseArray groups the indices and element values into their own lists. In[6]:= Out[6]=

The results of the two forms of SparseArray are identical. In[7]:= Out[7]=

SparseArray can also accept the dimensions of the matrix to be created. Here a 5×5 matrix is created even though the maximum explicit index was {2,3}. In[8]:= Out[8]= In[9]:= Out[9]//MatrixForm=

In this example the default value is set to 1; typically the default value is 0. In[10]:= Out[10]= In[11]:= Out[11]//MatrixForm=

Allowing the default value to be changed makes many element-wise operations very fast. They just need to work on the elements that are actually present and the default value. In[12]:= Out[12]= In[13]:= Out[13]//MatrixForm=

You can also give patterns for the rules. This can often be a convenient way to build structured matrices. You can use the names of the patterns on the right-hand side of the rules. Typically, it is better to use Band if this can be done, this is discussed in the section "Banded Sparse Arrays". In[14]:= Out[14]= In[15]:= Out[15]//MatrixForm=

You can use the Mathematica function Random to generate sparse arrays with entries that are pseudorandom numbers. You can also use Random to generate the indices for the sparse array. In this example a 10×10 sparse matrix with at most 50 nondefault entries is generated. In[16]:= Out[17]//MatrixForm=

If you want to use Random on the right-hand side of the rules in sparse array, or any other expression that will evaluate, you should use RuleDelayed (entered with ⧴) to form the rules. If you do not do this, the same number will be used throughout the sparse matrix. In[18]:= Out[19]//MatrixForm=

Rule Inputs for SparseArray

There are two different ways that rules can be used as input syntax for SparseArray. These are demonstrated here. In[1]:=

Both generate identical sparse arrays. In[3]:= Out[3]=

This uses SparseArray with many rules to mix explicit values with patterns. In[4]:= Out[5]//MatrixForm=

This demonstrates the form of SparseArray that uses only one rule. The timing is measured to demonstrate performance. In[6]:= Out[8]=

It is possible to convert the single rule to multiple rules using Thread. This takes more time than generating the sparse array. In[9]:= Out[9]=

This uses the multiple rule form of SparseArray. It is slower than the single rule form. In[10]:= Out[10]=

One reason why the single rule form of SparseArray is faster is that the indices and elements can use packed arrays, an efficient storage technology. If they are converted from packed arrays then SparseArray is slower as shown. In[11]:= Out[13]=

Banded Sparse Arrays

This creates a diagonal matrix. In[1]:= Out[1]//MatrixForm=

This has bands above and below the diagonal. In[2]:= Out[2]//MatrixForm=

This inserts a band along the anti-diagonal. In[6]:= Out[6]//MatrixForm=

Identity and Diagonal Sparse Matrices

This generates a 4×4 sparse identity matrix. In[1]:= Out[2]//MatrixForm=

This generates a 4×4 sparse diagonal matrix. In[3]:= Out[5]//MatrixForm=

If you want to compute with floating-point numbers it can be advantageous to use matrices that contain floating-point entries; this is described in more detail under "Matrix Contents". For IdentityMatrix you can use the WorkingPrecision option. In[6]:= Out[7]//MatrixForm=

For a diagonal matrix you can make sure that the diagonals already are machine precision numbers. In[8]:= Out[10]//MatrixForm=

Normal

To convert from a sparse array to the dense object that it represents, you can use Normal. In[1]:= Out[1]= In[2]:= Out[2]=

Of course, it is very straightforward to make a sparse array that cannot be represented on your system. For example, the following sparse matrix only has two nonzero elements, but it has 2499999998 zero elements. In[3]:= Out[3]=

If this is converted to a dense matrix, an exception is thrown because it is not possible to represent this on typical computers. In[4]:= Out[4]=

ArrayRules

SparseArray can accept a list of rules to form a sparse array. These rules hold the indices and values of nonzero elements. In the following example, the element at position {2,1} has the value 5. ArrayRules generates the rules for a sparse array. In[1]:= Out[1]=

ArrayRules returns the rules that represent the sparse array. It returns a rule of blank patterns {_, _} to show the default value. In[2]:= Out[2]=

When a scalar is added to the sparse array, the default value is changed. For example, here the default value is 5. In[3]:= Out[3]=

ArrayRules can take a second argument, which is the default value shown on output. Here, a default rule with value 5 is used. Because there is only one element with this value, the list of rules is much longer. In[4]:= Out[4]=

ArrayRules is a useful way to get information about a sparse array such as the nondefault elements or the default value. This example shows how to get the indices of the nondefault elements. In[5]:= Out[5]=

Structural Operations

Getting Pieces of Matrices

Ways to get pieces of matrices.

Here is a sample sparse matrix. In[1]:= Out[2]//MatrixForm=

This gets the third element in the first row. In[3]:= Out[3]=

This gets the third row; the row is returned as a sparse vector. In[4]:= Out[4]=

It can also obtain a column by using All to specify all rows; the column is returned as a sparse vector. In[5]:= Out[5]=

Negative indices are used to refer to the end of the matrix. The following gets the last element of the last row. In[6]:= Out[6]=

You can get ranges of a matrix using ;;. This gets the second through the fourth rows. In[7]:= Out[7]=

This gets the second through the fourth columns. In[8]:= Out[8]=

You can also give a step. This gets every other column. In[9]:= Out[9]=

The function Tr works on the diagonal elements of a matrix. The one-argument form adds them up. In[7]:= Out[7]=

Tr can also take a function as its second argument, which will apply to the diagonal elements. If List is used, this returns the diagonal elements. In[8]:= Out[8]=

Getting Multiple Pieces

It is possible to extract multiple elements by using indices in lists. This is demonstrated with the following sample matrix. In[1]:= Out[2]//MatrixForm=

The following gets the first and third elements of the third row. In[3]:= Out[3]=

The following gets the first and third rows. In[4]:= Out[4]=

The following gets the first and third elements of the first and second rows. In[5]:= Out[5]=

Setting Pieces of Matrices

Resetting parts of matrices.

Here is a sample sparse matrix. In[1]:= Out[2]//MatrixForm=

To update parts of a matrix you can use Part on the left-hand side of an assignment. This sets the third element of the third row. In[3]:= Out[4]//MatrixForm=

This sets the second row of the matrix. In[5]:= Out[6]//MatrixForm=

Here, the second column is set. In[7]:= Out[8]//MatrixForm=

You can also use the range syntax for setting pieces of the matrix. This sets every element in every other row to be z. In[9]:= Out[10]//MatrixForm=

Setting Multiple Pieces

It is possible to set multiple elements by using indices in lists. This is demonstrated with the following sample matrix. In[1]:= Out[2]//MatrixForm=

The following sets the first and third elements of the second row. In[3]:= Out[4]//MatrixForm=

If the right-hand side of the assignment is a list that matches the number of elements being assigned, the assignment is done element by element. Thus, the following gives two different values for the first and third elements of the second row. In[5]:= Out[6]//MatrixForm=

The following sets the second and third rows. In[7]:= Out[8]//MatrixForm=

The following gives two different values for the second and third rows. In[9]:= Out[10]//MatrixForm=

The following sets the first and third elements of the second and third rows. In[11]:= Out[13]//MatrixForm=

The following sets the first and third elements of the second and third rows with different values. In[14]:= Out[15]//MatrixForm=

Extracting Submatrices

Extracting submatrices.

In[1]:=

Out[2]//MatrixForm=

This extracts the submatrix from m2,1 to m3,2. In[3]:= Out[3]//MatrixForm=

This extracts the submatrix of rows 1 to 3. In[4]:= Out[4]//MatrixForm=

This extracts the submatrix of columns 2 to 4. In[5]:= Out[5]//MatrixForm=

You can use negative indices to count from the end. This returns the matrix with the first and last columns dropped. In[6]:= Out[6]//MatrixForm=

Deleting Rows and Columns