GNU Octave Manual Version 3by John W. Eaton, David Bateman, Søren Hauberg Paperback (6"x9"), 568 pages ISBN 095461206X RRP £24.95 ($39.95) |

### 20.1.1 Storage of Sparse Matrices

It is not necessary to know how sparse matrices are stored by Octave
in order to use them. However, knowledge of the storage technique is
helpful in estimating the memory requirements (and costs) of
operations involving sparse matrices. ^{(11)}

In general, there are many techniques for storing sparse matrix data,
each having different tradeoffs for different classes of operations.
A good summary of the available methods is given by Saad
^{(12)}.
One obvious way to store the elements of a sparse matrix M is as
a set of triplets containing the row and column of each non-zero
element and its value, (i,j,M_{ij)}. This is conceptually
simple but typically requires more memory than is actually needed.

The storage format used within Octave is *compressed column
format*. In this format, the non-zero values from each column and
their row positions are stored sequentially in memory. A separate
array records the locations which correspond to the start of each
column.

As an example, consider the matrix

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

The non-zero elements of this matrix are

(1, 1) => 1 (1, 2) => 2 (2, 4) => 3 (3, 4) => 4

This will be stored as three vectors `cidx`, `ridx` and `data`,
representing the column indexing, row indexing and data respectively. The
contents of these three vectors for the above matrix will be

cidx= [0, 1, 2, 2, 4]# column start index in ridx & dataridx= [0, 0, 1, 2]data= [1, 2, 3, 4]

Note that this is the C representation, with the first row and column
assumed to start at zero (in Octave the row and column indexing
starts at one). Thus the number of elements in the `i`-th column
is given by

.
`cidx` (`i` + 1) - `cidx` (`i`)

For simplicity, the column index contains one more entry than the number of columns, to record the position of the final element. The first element is always zero. This avoids any need to the handle the first and last columns as a special case.

The code to access the elements of a sparse matrix in C looks like this:

for (j = 0; j < nc; j++) for (i = cidx [j]; i < cidx[j+1]; i++) printf ("non-zero element (%i,%i) is %d\n", ridx[i], j, data[i]);

Note that Octave uses compressed column format, rather than compressed row format, for consistency with the column-major ordering of dense matrices. This makes operations that involve both sparse and dense matrices more efficient.

In the storage format used by Octave, sparse matrix elements are stored in increasing order of their row index. This requires sorting them on creation. Allowing disordered elements would make some operations faster (such as concatenating two matrices together) but would add complexity and reduce speed elsewhere.

ISBN 095461206X | GNU Octave Manual Version 3 | See the print edition |