SPARSE
MATLAB's Sparse Matrix Utility

SPARSE is a MATLAB routine for creating a sparse matrix, but we also intend to consider other features of MATLAB that make it easy to define and manipulate sparse matrices.

MATLAB's SPARSE function

MATLAB provides a sparse function of the form

matrix = sparse ( i, j, s, m, n, nz_max )

i

the row indices of the nonzero elements;

j

the column indices of the nonzero elements;

s

the values of the nonzero elements;

m

the number of rows in the matrix;

n

the number of columns in the matrix;

nz_max

the maximum number of nonzero elements in the matrix; nz_max is commonly omitted, in which case its value is taken from the length of s.

Example: Creating a Sparse Matrix at Once

Although this is not the usual way to use the sparse command, the following example should help to understand what is going on. We mean to define the following matrix:

        11  12   0   0  15
         0  22  23   0   0
        31   0  33  34  35
      

        i = [  1,  1,  1,  2,  2,  3,  3,  3,  3 ];
        j = [  1,  2,  5,  2,  3,  1,  3,  4,  5 ];
        s = [ 11, 12, 15, 22, 23, 31, 33, 34, 35 ];
        m = 3;
        n = 5;
        nz_max = 9;

        a = sparse ( i, j, s, m, n, nz_max );
      

Example: Building a Sparse Matrix in Steps

Of course, in many applications, the matrix data is only available one piece at a time, or has to be modified as you go. This is easy to do, as well. You can start by defining the matrix to be an "empty" sparse matrix of a particular size, as, for example:

        i = [];
        j = [];
        s = [];
        m = 100;
        n = 100;
        a = sparse ( i, j, s, m, n );
      

        a(1,1) = 3
        a(3,8) = a(3,8) + 7    
        a(4,7) = a(9,5) + 2 * a(8,12)
        a(4,7) = a(4,7) + 1
      

Useful Commands

In some cases, Matlab's sparse matrix structure allows you to ignore the fact that you are using a sparse matrix. We have already seen that you can reference the (i,j) element of the matrix in the same way you would do for a full matrix, and this is true whether you are simply asking to "read" the current value of the element, or to "write" a new value for the element.

A particular example of this is the fact that you can solve a sparse linear system using the same "backslash" formula that you would use if the matrix were full:

x = A \ b;

Matlab includes many commands specifically for dealing with a sparse matrix. For our examples, we will be considering

• nnz(A) returns the number of nonzero matrix elements;
• nzmax(A) returns the maximum number of nonzero matrix elements allocated;
• find(A) returns all (i,j) indices of nonzero elements;
• nonzeros(A) returns all the nonzero elements;

Note:

Note that, in a sense, MATLAB actually uses two formats for sparse matrices. The user communicates with MATLAB by specifying what is known as a sparse triplet, that is, a set of row indices, column indices, and values. But internally, MATLAB uses what is known as the sparse compressed column format. This format allows MATLAB to access matrix entries rapidly.

For details about the sparse compressed column format, refer to the SPARSE_CC web page listed below.

Related Data and Programs:

CSPARSE is a C library of routines for the direct solution of sparse linear systems.

DLAP is a FORTRAN90 library of routines for solving sparse linear systems.

FFH_SPARSE is a MATLAB program that solves the time dependent heat equation in an arbitrary triangulated 2D region, using MATLAB's sparse matrix storage format and solver.

FFNS_SPARSE is a MATLAB program for solving the incompressible steady Navier Stokes equations in an arbitrary 2D triangulated region, using MATLAB's sparse matrix storage, factorization and solution capabilities.

FFP_SPARSE is a MATLAB program that solves the Poisson equation in an arbitrary triangulated 2D region, using MATLAB's sparse matrix storage format and solver.

FFS_SPARSE is a MATLAB program for solving the incompressible steady Stokes equations in an arbitrary 2D triangulated region, using MATLAB's sparse matrix storage, factorization and solution capabilities.

HB_IO is a FORTRAN90 library of routines for reading and writing sparse linear systems stored in the Harwell-Boeing Sparse Matrix format.

HB_TO_MSM is a MATLAB program to convert a Harwell Boeing sparse matrix file to a MATLAB sparse matrix.

HB_TO_ST is an executable FORTRAN77 program which converts the sparse matrix information stored in a Harwell-Boeing file into a sparse triplet file.

LINPLUS is a MATLAB library of routines for linear algebra operations, which includes a set of operations for matrices in the "DCC" format, a format which is equivalent to MATLAB's sparse format.

MM_IO is a FORTRAN90 library of routines for reading and writing sparse linear systems stored in the Matrix Market format.

MSM_TO_HB is a MATLAB script which converts a MATLAB sparse matrix into a Harwell-Boeing file.

NSASM is a C library of routines, intended to be used with a MATLAB calling program, and which set up the sparse matrix needed for a Newton iteration to solve a finite element formulation of the steady incompressible 2D Navier Stokes equations.

NSPCG is a FORTRAN90 library of routines for nonsymmetric preconditioned conjugate gradient methods applied to sparse matrices.

SPARSE_CC is a data structure equivalent to MATLAB's sparse format, and a file format suitable for storing such information.

SPARSE_CR is a data directory which contains a description and examples of the CR format, ("compressed row") for storing a sparse matrix, including a way to write the matrix as a set of three files.

SPARSEKIT is a FORTRAN90 library of routines by Yousef Saad for sparse matrix operations.

SPARSEPAK is a FORTRAN90 library of routines that form an obsolete version of the Waterloo Sparse Matrix Package.

ST is the "sparse triplet" format for storing sparse matrices. This format is equivalent to the form in which sparse matrix data is passed into MATLAB's sparse command (although the sparse compressed column format is used internally).

TEMPLATES is a MATLAB library of routines for iterative solution of linear systems. It includes a routine mm_to_msm which can read a Matrix Market file and store it as a MATLAB sparse matrix.

TEST_MAT is a FORTRAN90 library of routines defining test matrices with known inverses, determinants, eigenvalues and so on.

Reference:

1. Timothy Davis,
   Direct Methods for Sparse Linear Systems,
   SIAM, 2006,
   ISBN: 0898716136.
2. Duane Hanselman, Bruce Littlefield,
   Mastering MATLAB 7,
   Pearson Prentice Hall, 2005,
   ISBN: 0-13-143018-1.
3. George Lindfield, John Penny,
   Numerical Methods Using MATLAB,
   Second Edition,
   Prentice Hall, 1999,
   ISBN: 0-13-012641-1,
   LC: QA297.P45.
4. The Mathworks,
   Using MATLAB, Version 6,
   The Mathworks, 2002.

Source Code:

• timestamp.m, prints the current YMDHMS date as a timestamp;

Examples and Tests:

• sparse_test.m, runs all the tests;
• sparse_test.out, is the output from the tests;
• sparse_test01.m, sets up a simple 3 by 5 matrix;
• sparse_test02.m, sets up a sparse -1,2,-1 matrix of order 100;
• sparse_test03.m, demonstrates the use of the SIZE, NNZ and FIND functions to describe the structure of a sparse matrix;
• sparse_test04.m, demonstrates that a sparse matrix can be constructed and incremented one element at a time;

You can go up one level to the MATLAB source codes.