HP MLIB User's Guide Vol. 2 7th Ed.

878 HP MLIB User’s Guide
What you need to know to use these subprograms
Sparsity and storage formats
Sparse matrices are matrices in which most of the entries are zero. The goal of
sparse matrix software is to take maximum advantage of these zero entries to
reduce storage and arithmetic. Storage is reduced by not storing zero entries;
arithmetic is reduced by not performing operations on entries that are known
to be zero.
It is easiest to see how to economize on storage. Suppose that an n-by-n matrix
A has only nz nonzero entries. Then A could be specified completely by storing
each of the nonzero values in an array of length nz that was accompanied by
two integer arrays of length nz holding the corresponding row and column
indices. Thus, 3nz storage suffices where n
2
storage is required for the
corresponding dense matrix format.
Consider, for example, the following matrix:
This matrix could be represented in the format described above by three arrays,
irow, jcol, and mxvalu, as shown in Table 13-1.
Figure 13-1 Row and Column Index Sparse Matrix Representation
In this example, the matrix entries have been listed in order within each
column, and the columns have been listed in order, although the representation
does not require that much structure.
11 0 13 14 0 0
0 22 23 0 25 0
31 32 33 0 35 0
41 0 0 44 45 0
052535455 0
0000066
irow
=
jcol
=
mxvalu
=
134235123514523456
11222333344455556
11 31 41 22 32 52 13 23 33 53 14 44 54 25 35 45 55 66
1