Accelerating the pace of engineering and science

Documentation

Accessing Sparse Matrices

Nonzero Elements

There are several commands that provide high-level information about the nonzero elements of a sparse matrix:

• nnz returns the number of nonzero elements in a sparse matrix.

• nonzeros returns a column vector containing all the nonzero elements of a sparse matrix.

• nzmax returns the amount of storage space allocated for the nonzero entries of a sparse matrix.

To try some of these, load the supplied sparse matrix west0479, one of the Harwell-Boeing collection.

whos

Name            Size             Bytes  Class     Attributes

M_full       1100x1100         9680000  double
M_sparse     1100x1100            5004  double    sparse
west0479      479x479            24564  double    sparse

This matrix models an eight-stage chemical distillation column.

Try these commands.

nnz(west0479)

ans =
1887

format short e
west0479

west0479 =

(25,1)      1.0000e+00
(31,1)     -3.7648e-02
(87,1)     -3.4424e-01
(26,2)      1.0000e+00
(31,2)     -2.4523e-02
(88,2)     -3.7371e-01
(27,3)      1.0000e+00
(31,3)     -3.6613e-02
(89,3)     -8.3694e-01
(28,4)      1.3000e+02
.
.
.

nonzeros(west0479);
ans =

1.0000e+00
-3.7648e-02
-3.4424e-01
1.0000e+00
-2.4523e-02
-3.7371e-01
1.0000e+00
-3.6613e-02
-8.3694e-01
1.3000e+02
.
.
.
 Note:   Use Ctrl+C to stop the nonzeros listing at any time.

Note that initially nnz has the same value as nzmax by default. That is, the number of nonzero elements is equivalent to the number of storage locations allocated for nonzeros. However, MATLAB® software does not dynamically release memory if you zero out additional array elements. Changing the value of some matrix elements to zero changes the value of nnz, but not that of nzmax.

However, you can add as many nonzero elements to the matrix as desired. You are not constrained by the original value of nzmax.

Indices and Values

For any matrix, full or sparse, the find function returns the indices and values of nonzero elements. Its syntax is

[i,j,s] = find(S)

find returns the row indices of nonzero values in vector i, the column indices in vector j, and the nonzero values themselves in the vector s. The example below uses find to locate the indices and values of the nonzeros in a sparse matrix. The sparse function uses the find output, together with the size of the matrix, to recreate the matrix.

[i,j,s] = find(S)
[m,n] = size(S)
S = sparse(i,j,s,m,n)

Indexing in Sparse Matrix Operations

Because sparse matrices are stored in compressed sparse column format, there are different costs associated with indexing into a sparse matrix than there are indexing into a full matrix. For example, consider the 4-by-4 identity matrix:

A=eye(4);

To replace the 2,1 entry with the number 3, you would do this:

A(2,1)=3

A =

1     0     0     0
3     1     0     0
0     0     1     0
0     0     0     1

Now suppose you were working on a sparse matrix:

B=speye(4);

The find command returns the indices and values of the nonzero components of a matrix:

[i,j,s]=find(B);
[i,j,s]

ans =

1     1     1
2     2     1
3     3     1
4     4     1

If you wanted to change a value in this matrix, you might be tempted to use the same indexing:

B(3,1) = 42;

This code does work, however, it is slow. Since MATLAB stores sparse matrices in compressed sparse column format, it needs to overwrite multiple entries in B.

[i,j,s]=find(B);
[i,j,s]

ans =

1     1     1
3     1    42
2     2     1
3     3     1
4     4     1

In order to store the new matrix with '42' at (3,1), MATLAB overwrites all matrix values after 3,1 and adds an additional row to the nonzero values vector and the row indices vectors.

Instead of using subscripted assignment, try using the sparse command to construct the matrix from the triplets. For example, suppose you wanted the sparse form of the coordinate matrix C:

$\text{C=}\begin{array}{rrrr}\hfill 4& \hfill 0& \hfill 0& \hfill -1\\ \hfill 0& \hfill 4& \hfill 0& \hfill -1\\ \hfill 0& \hfill 0& \hfill 4& \hfill -1\\ \hfill -1& \hfill -1& \hfill -1& \hfill 4\end{array}$

You can use indexing:

C=4*speye(4);
C(1:3,4)=-1;
C(4,1:3)=-1;

but this has the same issue that many of the entries in C need to be overwritten. If you use a loop, you exacerbate the inefficiency:

C=4*speye(4);
for k=1:3
C(k,4)=-1;
C(4,k)=-1;
end

Instead of rewriting every matrix entry when you want to rewrite one, construct the three-column matrix directly with the sparse function:

i = [1 4 2 4 3 4 1 2 3 4]';
j = [1 1 2 2 3 3 4 4 4 4]';
s = [4 -1 4 -1 4 -1 -1 -1 -1 4]';
CSP = sparse(i,j,s);

For more information on how MATLAB stores sparse matrices, see John R. Gilbert, Cleve Moler, and Robert Schreiber's Sparse Matrices In Matlab: Design and Implementation, (SIAM Journal on Matrix Analysis and Applications, 13:1, 333–356 (1992)).

Visualizing Sparse Matrices

It is often useful to use a graphical format to view the distribution of the nonzero elements within a sparse matrix. The MATLAB spy function produces a template view of the sparsity structure, where each point on the graph represents the location of a nonzero array element.

For example:

Load the supplied sparse matrix west0479, one of the Harwell-Boeing collection.