# 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 {i_{k},j_{k}} having value v_{k} | |

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 |

### SparseArray

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

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.

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

#### Rule Inputs for SparseArray

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.

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 {i,j} |

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

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

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 |

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

### ArrayRules

## 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 i,j ^{th} entry |

m[[i]] | the i ^{th} row |

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

m[[All,i]] | the i ^{th} 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 i_{k} and column indices j_{k} |

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

Ways to get pieces of matrices.

#### Getting Multiple Pieces

### 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 {i,j} 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 {v_{1},v_{2},…} |

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 {v_{1},v_{2},…} |

#### Setting Multiple Pieces

### 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 i_{0} through i_{1} and columns j_{0} through j_{1} |

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

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

### Deleting Rows and Columns

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

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

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

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

### 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 |

### Extending Matrices

### Transpose

### Rotating Elements

### 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 |

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 m_{1} and m_{2} |

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

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

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

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

### Listability

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 fun[0] is only computed once.

### Map

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

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".

## 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.

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

## Matrix Multiplication

### Outer Product

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.

## 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.

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.

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.