WOLFRAM

Wolfram Language & System Documentation Center

Working with Sparse Arrays

Additional functionality related to this tutorial has been introduced in subsequent versions of the Wolfram Language. For the latest information, see Matrices and Linear Algebra.
Basic OperationsMatrix Multiplication
Structural OperationsMatrix Permutations
Element-wise OperationsConverting Equations to Sparse Arrays
Visualization of Sparse MatricesSparseArray Data Format
Import and Export of Sparse Matrices

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. Wolfram Language offers a sparse representation for matrices, vectors, and tensors with SparseArray.

This tutorial discusses how to create and work with SparseArray objects in Wolfram Language. 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 Wolfram Language is a SparseArray.

SparseArray[list]a SparseArray version of an ordinary list
SparseArray[{{i1,j1}->v1,{i2,j2}->v2,…},{m,n}]
an m×n sparse array with element {ik,jk} having value vk
SparseArray[{{i1,j1},{i2,j2},…}->{v1,v2,…},{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
A SparseArray object can be created by giving a list of those elements that are nonzero:
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:
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:
Listable operations also work on sparse arrays to thread over all elements:
All combinations of matrix multiplication using the function Dot are supported. This demonstrates the dot product of two sparse arrays:
This demonstrates the dot product of a sparse array with a dense vector:
The dot product of a sparse array with a dense matrix is supported:
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:
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:
If the N command is applied to a sparse matrix, it works on all the elements. This builds an example 3×3 sparse matrix:
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:
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:

SparseArray

The main function for generating a sparse array is SparseArray. This can operate on a matrix to generate its sparse representation:
SparseArray can also take a list of rules showing the values for certain parts:
An equivalent syntax for SparseArray groups the indices and element values into their own lists:
The results of the two forms of SparseArray are identical:

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

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 this example the default value is set to 1; typically the default value is 0:
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:
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":

Wolfram Language 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.

You can use the Wolfram Language 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:
If you want to use Random on the right-hand side of the rules in a sparse array, or in 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:

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

Rule Inputs for SparseArray

There are two different ways that rules can be used as input syntax for SparseArray. These are demonstrated here:
Both generate identical sparse arrays:

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.

This uses SparseArray with many rules to mix explicit values with patterns:
This demonstrates the form of SparseArray that uses only one rule. The timing is measured to demonstrate performance:
It is possible to convert the single rule to multiple rules using Thread. This takes more time than generating the sparse array:
This uses the multiple rule form of SparseArray. It is slower than the single rule form:
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:

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[{imin,jmin},{imax,imax}]a diagonal band from {imin,jmin} to {imax,imax}
Band[{imin,jmin},{imax,imax}{di,dj}]a diagonal band from {imin,jmin} moving with step {di,dj}
This creates a diagonal matrix:
This has bands above and below the diagonal:
This inserts a band along the anti-diagonal:

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 Wolfram Language.

IdentityMatrix[n,Sparse->True]a sparse identity matrix
DiagonalMatrix[SparseArray[{a,b,c,d}]]
a sparse diagonal matrix
This generates a 4×4 sparse identity matrix:
This generates a 4×4 sparse diagonal matrix:
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:
For a diagonal matrix, you can make sure that the diagonals already are machine-precision numbers:

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 Wolfram Language can work with are described in more detail under "Matrix Types".

Normal

To convert from a sparse array to the dense object that it represents, you can use Normal:
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:
If this is converted to a dense matrix, an exception is thrown because it is not possible to represent this on typical computers:

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:
ArrayRules returns the rules that represent the sparse array. It returns a rule of blank patterns {_,_} to show the default value:
When a scalar is added to the sparse array, the default value is changed. For example, here the default value is 5:
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:
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:

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 Wolfram Language 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[[{i1,…,ir},{j1,…,js}]]the r×s submatrix with elements having row indices ik and column indices jk
Tr[m,List]list of the diagonal elements of m

Ways to get pieces of matrices.

Here is a sample sparse matrix.
This gets the third element in the first row:
This gets the third row; the row is returned as a sparse vector:
It can also obtain a column by using All to specify all rows; the column is returned as a sparse vector:
Negative indices are used to refer to the end of the matrix. The following gets the last element of the last row:
You can get ranges of a matrix using ;;. This gets the second through the fourth rows:
This gets the second through the fourth columns:
You can also give a step. This gets every other column:
The function Tr works on the diagonal elements of a matrix. The one-argument form adds them up:
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:

Getting Multiple Pieces

It is possible to extract multiple elements by using indices in lists. This is demonstrated with the following sample matrix.
The following gets the first and third elements of the third row:
The following gets the first and third rows:
The following gets the first and third elements of the first and second rows:

Setting Pieces of Matrices

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

m={{a11,a12,…},{a21,a22,…},…}assign m to be a matrix
m[[i,j]]=vreset element {i,j} to be v
m[[i]]=vreset all elements in row i to be v
m[[i]]={v1,v2,…}reset elements in row i to be {v1,v2,…}
m[[All,j]]=vreset all elements in column j to be v
m[[All,j]]={v1,v2,…}reset elements in column j to be {v1,v2,…}

Resetting parts of matrices.

Here is a sample sparse matrix:
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:
This sets the second row of the matrix:
Here, the second column is set:
You can also use the range syntax for setting pieces of the matrix. This sets every element in every other row to be z:

Setting Multiple Pieces

It is possible to set multiple elements by using indices in lists. This is demonstrated with the following sample matrix:
The following sets the first and third elements of the second row:
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:
The following sets the second and third rows:
The following gives two different values for the second and third rows:
The following sets the first and third elements of the second and third rows:
The following sets the first and third elements of the second and third rows with different values:

Extracting Submatrices

The range syntax is useful to extract a submatrix.

m[[i0;;i1,j0;;j1]]extract the submatrix with rows i0 through i1 and columns j0 through j1
m[[i0;;i1]]extract the submatrix with rows i0 through i1
m[[All,j0;;j1]]extract the submatrix with columns j0 through j1

Extracting submatrices.

This extracts the submatrix from m2,1 to m3,2:
This extracts the submatrix of rows 1 to 3:
This extracts the submatrix of columns 2 to 4:
You can use negative indices to count from the end. This returns the matrix with the first and last columns dropped:

Deleting Rows and Columns

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

Drop[m,{i0,i1}]delete rows i0 through i1
Drop[m,{},{j0,j1}]delete columns j0 through j1
Drop[m,{i0,i1},{j0,j1}]delete rows i0 through i1 and columns j0 through j1

Deleting rows and columns.

This drops rows 2 through 4:
This drops columns 2 through 4:
In this example, rows 2 and 3, and columns 1, 2, and 3 are all dropped:

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

Inserting a row.

This inserts a row before row 3:
If you want to insert a column, you must transpose the matrix, insert the column as a row, and then transpose the matrix back. This inserts a column before column 5:

Extending Matrices

You can increase the size of a matrix by padding it with PadLeft and PadRight.
PadLeft adds the elements to the beginning of the matrix. This example returns a 4×4 sparse matrix:
You can see the result with MatrixForm:
PadRight adds the elements to the end of the matrix; the result is a sparse array:
You can use PadLeft to pad on the right if you specify negative indices:
One important use of the padding functions is to replicate and tile a matrix. In this example, the input matrix is extended to have two versions in every row and three in every column.
PadLeft and PadRight have a number of extra features. These are described in the Wolfram Language documentation.

Transpose

Transposition of elements is a general matrix operation:
Transpose swaps elements at specific indices; the result is a sparse array:
If you wish to compute the conjugate transpose of a sparse matrix, you can use ConjugateTranspose:
If a matrix is equal to its conjugate transpose, it is said to be Hermitian:
You can also test with the function HermitianMatrixQ:

Rotating Elements

Another structural operation is to rotate elements within an index. This can be done with the functions RotateLeft and RotateRight:
This rotates left by one step in the first level, thereby operating on the rows; the result is a sparse array:
This rotates left by one step in the second level that operates on the columns; the result is a sparse array:
This rotates the columns in the opposite direction:

Testing Matrices

Wolfram Language 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
mi==mjcompare two matrices for equality
The predicate MatrixQ can be used to test sparse matrices. It can also be used to test dense matrices as shown previously.
This tests that sp is a sparse matrix:
MatrixQ takes an optional second argument that specifies a test to apply to every element. In this example, every element is tested to see if it is an integer:
In this example, every element must be an integer greater than 1. Because some of the elements are 0, the result is False:
In addition to MatrixQ, there are predicates VectorQ and ArrayQ, which are useful for testing vectors and tensors:
ArrayQ can also take a rank argument to test the depth of the array. In this example, the sparse argument is not a rank-4 tensor, and the result is False:
ArrayQ also takes a third argument that tests each element. In this example, the result is True because all the elements are NumberQ:
The command Dimensions is useful for extracting size information:
Dimensions returns a list of length 2 when the input is a matrix, stating that two indices are used to reference any element in the matrix. Another way to test the number of indices required to reference elements is with ArrayDepth; this is equivalent to Length[Dimensions[sp]]:
To compare if the elements of two matrices are equal, it is possible to use Equal, typically entered using a == shorthand notation. For example, comparing a matrix with itself returns True:
Equal uses the value of numbers, so it can be used to compare integer and real values:

It should be noted that Equal works on any Wolfram Language 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[m1,m2]concatenate m1 and m2
Append[m,r]insert row r at the end of m
Prepend[m,r]insert row r at the beginning of m
This generates a sample matrix for demonstration:
This flattens the matrix into a vector:
The vector can be partitioned back into a matrix with rows of length 3 using Partition:
Matrices can be joined together with the function Join:
Alternatively, you can join the new matrix as new columns:
A new row can be inserted at the end of a matrix with Append:

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

If you want to work on the elements of a sparse matrix, you can do this easily with Wolfram Language. First, a matrix of floating-point numbers is created:
In general, arithmetic operations applied to a matrix work on each element. This adds 5 to the matrix:
Here, every element of the matrix is squared:
If one matrix is divided by another, the division is done element by element. If the dimensions of the two matrices do not agree, then an error ensues:
To apply the Sin function to every element, you apply Sin to the entire matrix:
If both of the arguments of an operation are matrices, the operation is carried out on corresponding elements. This result is the same as multiplying the matrix by two:
If one argument is a matrix and the other is a vector, the operation is carried out between rows of the matrix and elements of the vector. This is an efficient way of generating a diagonal sparse matrix:

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

Note that multiplying two matrices using the operator Times is equivalent to multiplying the corresponding elements. On the other hand, matrix multiplication can be done with the function Dot, which is described in the section "Matrix Multiplication". Element-wise multiplication is shown in the following example:

Listability

If you want to apply your own function to each element in a matrix, you may give your function the attribute Listable. This function squares each element and divides the result by 3:

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

Instead of using listability, you can use Map to apply a function to every element in a matrix.
Map will apply the function fun to every element in the matrix:
You can see the matrix that the sparse array represents. Note that because the function f did not have any definition, it is just kept wrapped around every element:
Here, a function that squares its argument and divides the result by 5 is applied to every element in the matrix:

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

Sparse matrices can be formatted with the function MatrixForm:
MatrixForm also works for vectors and higher-rank sparse arrays; the braces can help in understanding the grouping:

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

This reads in a sparse matrix, using the Import function demonstrated in the previous section:
The matrix can be plotted. This is a useful way to see the structure of the matrix:
If the matrix is multiplied with itself, the result is less sparse, but it still has a related structure:

Import and Export of Sparse Matrices

Wolfram Language 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 Wolfram Language 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 Wolfram Language 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.

There are two formats that are specific to sparse matrices and are supported in Wolfram Language: "Harwell–Boeing" and "Matrix Market". This example imports the matrix in the file dwg961b.cua using the Harwell–Boeing format:
The result is a 961×961 matrix of numbers with 10591 nonzero elements:
You can confirm the dimensions of the matrix:
If the matrix is multiplied with itself, the result may not be as sparse as before:

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

Matrix Multiplication

Matrix multiplication is carried out in Wolfram Language with the function Dot, which is typically entered with a dot shorthand syntax. The operation is fully supported for sparse arrays:
The sparse matrix can be multiplied by itself; the result is also a sparse matrix:
This multiplies a sparse matrix by a dense vector. In this case the result is dense:
If the vector is made into a sparse array, the result of the multiplication will be sparse:
In general, the result of matrix multiplication will be sparse if both arguments are sparse. This is not true if the default values are different:
What is particularly important about sparse matrix vector multiplication is that it is fast. In this example, a 100000×100000 tri-diagonal sparse matrix is multiplied by a dense vector:
Another issue with multiplication of sparse and dense matrices is that there are differences in the speed of computation depending on whether the dense matrix is on the left or the right:
The first example is slower than the second, even though the result is the same in both cases:
One possibility to improve the speed is to convert the dense matrix to a sparse representation. Now the result is a sparse matrix:
Another solution would be to reverse the order by working with the transpose of each matrix:

Outer Product

The outer product is a way to build a higher-rank tensor from ones of lower rank. Wolfram Language 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:

This generation of sparse outer products can be very advantageous if you want to use Wolfram Language 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 Wolfram Language 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]]=mapply the inverse of a permutation to the rows of a matrix
m[[All,perm]]=mapply the inverse of a permutation to the columns of a matrix

Applying permutations to matrices.

This generates a random matrix:
Now the matrix will be reordered so that the rows with smallest 2-norm are first. ("Norms" are discussed under "Matrix Computations".) First, the norm of each row is computed:
This computes the permutation that is necessary to reorder the matrix:
This applies the ordering to the rows of the matrix; the result has rows with smallest 2-norms first:
Now the inverse permutation is applied using part assignment. Note that this modifies the matrix held by the symbol pmat. Part assignment is described previously:

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. Wolfram Language 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.

These equations can be solved with the algebraic equation solver, Solve:
However, it is a bit more involved to go from the equation to the matrix representation. Wolfram Language 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:
You can see the details of the sparse arrays with MatrixForm:
CoefficientArrays is general and will work for nonlinear as well as linear polynomial equations:
When the input is a nonlinear polynomial, the result will include higher-rank tensors:
You can still regain the original expressions with dot products:

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. Wolfram Language uses the Compressed Sparse Row (CSR) format as an internal storage format. This can be explained for a sample matrix shown here.

You can see the internal form in the InputForm of the matrix:

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.