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 withSparseArray.
This tutorial discusses how to create and work withSparseArray 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 aSparseArray.
| SparseArray[list] | aSparseArray version of an ordinary list |
| SparseArray[{{i1,j1}->v1,{i2,j2}->v2,…},{m,n}] |
| anm×n sparse array with element{ik,jk} having valuevk |
| SparseArray[{{i1,j1},{i2,j2},…}->{v1,v2,…},{m,n}] |
| the same sparse array |
| SparseArray[data,{m,n},def] | anm×n sparse array with default elementdef |
| SparseArray[Band[b]->v,{m,n}] | anm×n banded sparse array |
| Normal[array] | the ordinary list corresponding to aSparseArray |
| 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 withSparseArray 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 withBand.
| SparseArray[Band[b]->v,{m,n}] | anm×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 useBand 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.
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 functionPart. TypicallyPart is entered with[[]] notation.
| m[[i,j]] | thei,jth entry |
| m[[i]] | theith row |
| m[[i;;j]] | rowsi throughj |
| m[[All,i]] | theith column |
| m[[All,i;;j]] | columnsi throughj |
| m[[{i1,…,ir},{j1,…,js}]] | ther×s submatrix with elements having row indicesik and column indicesjk |
| Tr[m,List] | list of the diagonal elements ofm |
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 functionPart on the left-hand side of an assignment.
| m={{a11,a12,…},{a21,a22,…},…} | assignm to be a matrix |
| m[[i,j]]=v | reset element{i,j} to bev |
| m[[i]]=v | reset all elements in rowi to bev |
| m[[i]]={v1,v2,…} | reset elements in rowi to be{v1,v2,…} |
| m[[All,j]]=v | reset all elements in columnj to bev |
| m[[All,j]]={v1,v2,…} | reset elements in columnj 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 rowsi0 throughi1 and columnsj0 throughj1 |
| m[[i0;;i1]] | extract the submatrix with rowsi0 throughi1 |
| m[[All,j0;;j1]] | extract the submatrix with columnsj0 throughj1 |
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 useDrop.
| Drop[m,{i0,i1}] | delete rowsi0 throughi1 |
| Drop[m,{},{j0,j1}] | delete columnsj0 throughj1 |
| Drop[m,{i0,i1},{j0,j1}] | delete rowsi0 throughi1 and columnsj0 throughj1 |
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 useInsert.
| Insert[m,r,i] | insert rowr into matrixm at positioni |
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:
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:
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] | giveTrue ifexpr has the form of a vector, andFalse otherwise |
| MatrixQ[expr] | giveTrue ifexpr has the form of a matrix, andFalse otherwise |
| ArrayQ[t,n] | test whethert is a tensor of rankn |
| Dimensions[expr] | a list of the dimensions of a vector or matrix |
| ArrayDepth[t] | find the rank of a tensor |
| mi==mj | compare 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 thatEqual 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 inm |
| Flatten[m,n] | flatten out nested lists inm to leveln |
| Partition[m,n] | partitionm into sublists of lengthn |
| Join[m1,m2] | concatenatem1 andm2 |
| Append[m,r] | insert rowr at the end ofm |
| Prepend[m,r] | insert rowr at the beginning ofm |
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 withInsert. 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 offun[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:
WhenMap 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 ofmat |
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 fromMatrixForm 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 functionMatrixPlot, which is described in greater detail under "Plotting Matrices".
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 functionsImport andExport are useful. TheImport 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 athttp://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 functionPart 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.
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.
