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

GNU Octave Manual Version 3 Buy the book here >>> learn more

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. ⁽¹¹⁾

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 ⁽¹²⁾. 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 & data
  ridx = [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.