*Mathematica*. For the latest information, see Matrices and Linear Algebra.

# Working with Sparse Arrays

Sparse representations of matrices are useful because they do not store every element. If one particular value appears very frequently it can be very advantageous to use a sparse representation. *Mathematica* offers a sparse representation for matrices, vectors, and tensors with SparseArray.

This tutorial discusses how to create and work with SparseArray objects in *Mathematica*. If you are interested in carrying out linear algebra computations on sparse matrices, you should consult "Matrix Computations".

## Basic Operations

The basic object for representing a sparse matrix in *Mathematica* is a SparseArray.

SparseArray[list] | a SparseArray version of an ordinary list |

SparseArray[{{i_{1},j_{1}}->v_{1},{i_{2},j_{2}}->v_{2},...},{m,n}] | |

an m×n sparse array with element having value | |

SparseArray[{{i_{1},j_{1}},{i_{2},j_{2}},...}->{v_{1},v_{2},...},{m,n}] | |

the same sparse array | |

SparseArray[data,{m,n},def] | an m×n sparse array with default element def |

SparseArray[Band[b]->v,{m,n}] | an m×n banded sparse array |

Normal[array] | the ordinary list corresponding to a SparseArray |

ArrayRules[m] | positions of nonzero elements |

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]//MatrixForm= | |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]= |

In[12]:= |

Out[12]= |

In[13]:= |

Out[14]//MatrixForm= | |

In[15]:= |

Out[15]//MatrixForm= | |

In[16]:= |

Out[16]//MatrixForm= | |

### SparseArray

In[1]:= |

Out[2]= |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]= |

A fuller discussion of the relative advantages of the two forms is given in the section "Rule Inputs for SparseArray".

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]//MatrixForm= | |

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]//MatrixForm= | |

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]//MatrixForm= | |

In[14]:= |

Out[14]= |

In[15]:= |

Out[15]//MatrixForm= | |

*Mathematica* uses symbolic algebraic techniques to simplify certain of the patterns for building sparse arrays. This allows it to construct the sparse array without testing every potential element to see if it is actually present in the array, thus providing a significant saving in computational time.

*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= | |

In[18]:= |

Out[19]//MatrixForm= | |

The general principle is that the rules you use with SparseArray work in the typical way for rules in *Mathematica*.

#### Rule Inputs for SparseArray

In[1]:= |

In[3]:= |

Out[3]= |

The first form, which has many rules, is convenient if you want to mix explicit indices with patterns. It is also more readable for small examples. The second is more efficient, and is preferred if you only have explicit indices, for example, after reading data from a file.

In[4]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

In[11]:= |

Out[13]= |

More information on packed arrays is found under "Packed Arrays".

### Banded Sparse Arrays

If you want to build sparse matrices that have some type of banded structure, this can be achieved with Band.

SparseArray[Band[b]->v,{m,n}] | an m×n banded sparse array |

Band[{i,j}] | a diagonal band that starts with the position |

Band[{i_{min},j_{min}},{i_{max},i_{max}}] | a diagonal band from to |

Band[{i_{min},j_{min}},{i_{max},i_{max}}{d_{i},d_{j}}] | a diagonal band from moving with step |

In[1]:= |

Out[1]//MatrixForm= | |

In[2]:= |

Out[2]//MatrixForm= | |

In[6]:= |

Out[6]//MatrixForm= | |

In general, if you can use Band to create a sparse array, it will be more efficient.

### Identity and Diagonal Sparse Matrices

There are a number of ways to create identity and diagonal sparse matrices in *Mathematica*.

IdentityMatrix[n,Sparse->True] | a sparse identity matrix |

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

a sparse diagonal matrix |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[7]//MatrixForm= | |

In[8]:= |

Out[10]//MatrixForm= | |

Notice how all the entries of the matrix are machine-precision numbers. This can help to improve the efficiency of your computations. The different types of matrices that *Mathematica* can work with are described in more detail under "Matrix Types".

### Normal

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

### ArrayRules

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

## Structural Operations

Structural operations on sparse arrays are all equivalent to the operations on dense matrices.

### Getting Pieces of Matrices

Extracting elements, rows, and columns of a sparse matrix is quite straightforward with the *Mathematica* function Part. Typically Part is entered with notation.

m[[i,j]] | the entry |

m[[i]] | the i row |

m[[i;;i]] | rows i through j |

m[[All,i]] | the i column |

m[[All,i;;j]] | columns i through j |

m[[{i_{1},...,i_{r}},{j_{1},...,j_{s}}]] | the r×s submatrix with elements having row indices and column indices |

Tr[m,List] | list of the diagonal elements of m |

Ways to get pieces of matrices.

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

#### Getting Multiple Pieces

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

### Setting Pieces of Matrices

Setting elements, rows, and columns so that a sparse matrix is updated is quite straightforward by using the *Mathematica* function Part on the left-hand side of an assignment.

m={{a_{11},a_{12},...},{a_{21},a_{22},...},...} | assign m to be a matrix |

m[[i,j]]=v | reset element to be v |

m[[i]]=v | reset all elements in row i to be v |

m[[i]]={v_{1},v_{2},...} | reset elements in row i to be |

m[[All,j]]=v | reset all elements in column j to be v |

m[[All,j]]={v_{1},v_{2},...} | reset elements in column j to be |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[8]//MatrixForm= | |

In[9]:= |

Out[10]//MatrixForm= | |

#### Setting Multiple Pieces

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[8]//MatrixForm= | |

In[9]:= |

Out[10]//MatrixForm= | |

In[11]:= |

Out[13]//MatrixForm= | |

In[14]:= |

Out[15]//MatrixForm= | |

### Extracting Submatrices

The range syntax is useful to extract a submatrix.

m[[i_{0};;i_{1},j_{0};;j_{1}]] | extract the submatrix with rows through and columns through |

m[[i_{0};;i_{1}]] | extract the submatrix with rows through |

m[[All,j_{0};;j_{1}]] | extract the submatrix with columns through |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[6]//MatrixForm= | |

### Deleting Rows and Columns

If you want to delete rows or columns, you can use Drop.

Drop[m,{i_{0},i_{1}}] | delete rows through |

Drop[m,{},{j_{0},j_{1}}] | delete columns through |

Drop[m,{i_{0},i_{1}},{j_{0},j_{1}}] | delete rows through and columns through |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]//MatrixForm= | |

### Inserting Rows and Columns

If you want to insert a row, you can use Insert.

Insert[m,r,i] | insert row r into matrix m at position i |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]//MatrixForm= | |

### Extending Matrices

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[8]//MatrixForm= | |

In[9]:= |

Out[9]//MatrixForm= | |

*Mathematica*documentation.

### Transpose

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[7]//MatrixForm= | |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

### Rotating Elements

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[6]//MatrixForm= | |

### Testing Matrices

*Mathematica* provides a number of functions for testing sparse matrices and extracting size information.

VectorQ[expr] | give True if expr has the form of a vector, and False otherwise |

MatrixQ[expr] | give True if expr has the form of a matrix, and False otherwise |

ArrayQ[t,n] | test whether t is a tensor of rank n |

Dimensions[expr] | a list of the dimensions of a vector or matrix |

ArrayDepth[t] | find the rank of a tensor |

m_{i}==m_{j} | compare two matrices for equality |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[10]:= |

Out[11]//MatrixForm= | |

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]= |

In[14]:= |

Out[15]= |

In[16]:= |

Out[16]= |

It should be noted that Equal works on any *Mathematica* expression. If you want to compare two matrices for equality using properties of the matrix as a whole, it may be better to compare matrix norms. These are discussed under "Matrix Norms".

### Further Structural Operations

This section discusses some further structural operations that are useful for working with matrices.

Flatten[m] | flatten out nested lists in m |

Flatten[m,n] | flatten out nested lists in m to level n |

Partition[m,n] | partition m into sublists of length n |

Join[m_{1},m_{2}] | concatenate and |

Append[m,r] | insert row r at the end of m |

Prepend[m,r] | insert row r at the beginning of m |

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[4]= |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[7]//MatrixForm= | |

In[8]:= |

Out[8]//MatrixForm= | |

It should be noted that this can also be done with Insert. This is shown in the section "Inserting Rows and Columns".

## Element-wise Operations

*Mathematica*. First, a matrix of floating-point numbers is created.

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]//MatrixForm= | |

In[6]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[7]//MatrixForm= | |

In[8]:= |

Out[10]//MatrixForm= | |

In[11]:= |

Out[11]= |

In[12]:= |

Out[12]//MatrixForm= | |

These operations are all fast because they only need to operate on the elements that are actually stored (including the default element).

In[8]:= |

Out[9]//MatrixForm= | |

### Listability

In[1]:= |

In[3]:= |

In[4]:= |

Out[4]//MatrixForm= | |

When a listable operation is applied to a sparse array, it only operates on the elements that are actually stored (including the default element), so the value of is only computed once.

### Map

In[1]:= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]//MatrixForm= | |

When Map applies a function to a sparse array, it only operates on the elements that are actually stored (including the default element).

## Visualization of Sparse Matrices

This section reviews the functions that are available for formatting and plotting sparse matrices. Because sparse matrices are well integrated into the system, most of the examples in this section are very similar to the way that dense matrices work. Visualization techniques for dense matrices are described under "Visualization of Matrices".

MatrixForm[mat] | print a matrix with the elements arranged in a two-dimensional array |

MatrixPlot[mat] | show the structural pattern of mat |

### Formatting Sparse Matrices

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]//MatrixForm= | |

The view that you get from MatrixForm is dense, which can help you see the sparsity pattern. However, it can quickly lead to very large output, especially as the rank of the array increases.

### Plotting Sparse Matrices

A convenient way to plot sparse matrices is with the function MatrixPlot, which is described in greater detail under "Plotting Matrices".

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

## Import and Export of Sparse Matrices

*Mathematica* provides a number of different tools for I/O. You can save your data in a file so that you or a colleague can continue to work with it in *Mathematica* later. For this you might want to use some of the expression I/O functions; these are discussed under "Expression Input and Output".

If you want to work with matrices from a source external to *Mathematica* using specific data formats, the functions Import and Export are useful. The Import function supports a variety of different formats, some of which are relevant to sparse matrices.

*Mathematica*: "Harwell-Boeing" and "Matrix Market". This example imports the matrix in the file using the Harwell-Boeing format.

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

Many examples of matrices in Harwell-Boeing and Matrix Market formats can be found at http://math.nist.gov/MatrixMarket/index.html.

## Matrix Multiplication

*Mathematica*with the function Dot, which is typically entered with a dot shorthand syntax. The operation is fully supported for sparse arrays.

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]//MatrixForm= | |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]//MatrixForm= | |

In[8]:= |

Out[8]= |

In[9]:= |

In[11]:= |

Out[11]= |

In[12]:= |

In[14]:= |

Out[14]= |

In[15]:= |

Out[15]= |

In[16]:= |

Out[17]= |

In[18]:= |

Out[18]= |

### Outer Product

*Mathematica*provides this functionality with the function Outer. One use of this is to combine two vectors to form a matrix as an outer product. This works for sparse vector input to generate a sparse array.

In[1]:= |

Out[3]= |

In[4]:= |

Out[4]//MatrixForm= | |

This generation of sparse outer products can be very advantageous if you want to use *Mathematica* sparse arrays as general sparse data structures.

## Matrix Permutations

Many matrix techniques rely on ordering a matrix in particular ways. For example, some techniques try to order the matrix to put elements on the diagonal, while others try to group certain elements into dense blocks. The *Mathematica* function Part is very well suited to applying permutations to the rows and columns of a matrix.

m[[perm]] | apply a permutation to the rows of a matrix |

m[[All,perm]] | apply a permutation to the columns of a matrix |

m[[perm,perm]] | apply a permutation to the rows and columns of a matrix |

m[[perm]]=m | apply the inverse of a permutation to the rows of a matrix |

m[[All,perm]]=m | apply the inverse of a permutation to the columns of a matrix |

Applying permutations to matrices.

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[6]//MatrixForm= | |

In[7]:= |

Out[8]//MatrixForm= | |

## Converting Equations to Sparse Arrays

Matrices are so important in many areas of science and technology because they are an efficient way to represent linear systems of equations. *Mathematica* is unique among technical computing systems in that it combines very efficient ways to work with matrices and also with the equations that the matrices represent. It is easy to go from a matrix to a system of equations and back. Here, a sparse matrix is multiplied by a vector of the unknowns and a system of equations is formed.

In[1]:= |

Out[2]= |

In[3]:= |

Out[3]//MatrixForm= | |

In[4]:= |

Out[4]= |

*Mathematica*provides the function CoefficientArrays to make this transformation easier. This takes the equations that were generated; the result is a list of a sparse vector and a sparse matrix.

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

The ability to work directly with systems of linear equations can be very advantageous for certain applications. For example, generating finite difference solutions. This is demonstrated in the example "Finite Difference Solutions".

## SparseArray Data Format

There are several different formats that can be used to hold sparse arrays. Each has its own advantages and disadvantages. *Mathematica* uses the Compressed Sparse Row (CSR) format as an internal storage format. This can be explained for a sample matrix shown here.

In[1]:= |

Out[2]//MatrixForm= | |

In[3]:= |

Out[3]//InputForm= | |

This format is general enough to describe arbitrary rank tensors. Other advantages of the format include the fact that data elements in the same row are stored next to each other, which leads to better cache performance. A disadvantage is that it is not optimized for inserting new elements into the matrix.