Page 90 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 6: Operations on Arrays and Sparse Matrices

elements. On the other hand, they are not very efficient, needing an indirect addressing step for Notes
every single scalar operation in a matrix-vector product or preconditioner solve.
The compressed row storage (CRS) format puts the subsequent non-zeros of the matrix rows in
contiguous memory locations. Assuming we have a non-symmetric sparse matrix A, we create
three vectors: one for floating point numbers (val) and the other two for integers (col_ind,
row_ptr). The val vector stores the values of the non-zero elements of the matrix A as they are
traversed in a row-wise fashion. The col_ind vector stores the column indexes of the elements in
the val vector. That is, if val(k) = a , then col_ind(k) = j. The row_ptr vector stores the locations in
i,j
the val vector that start a row; that is, if val(k) = a , then row_ptr(i) ≤ k < row_ptr(i + 1). By
i,j
convention, we define row_ptr(n + 1) = nnz + 1, where nnz is the number of non-zeros in the
matrix A. The storage savings for this approach is significant. Instead of storing n elements, we
2
need only 2nnz + n + 1 storage locations.
As an example, consider the non-symmetric matrix A defined by

Figure 6.4: Non-symmetric Matrix A

1000 0 − 2 0
3 9 0 0 0 3
0 7 8 7 0 0
A =
3 0 8 7 5 0
0 809 9 13
0 400 2 − 1

The CRS format for this matrix is then specified by the arrays {val, col_ind, row_ptr} given
below:

Figure 6.5: CRS Format for Matrix A given in Figure 6.4

val 10 -2 3 9 3 7 8 7 3 9 13 4 2 -1

col_ind 1 5 1 2 6 2 3 4 1 5 6 2 5 6

row_ptr 1 3 6 9 13 17 20

If the matrix A is symmetric, we need only store the upper (or lower) triangular portion of the
matrix.

Notes The tradeoff is a more complicated algorithm with a somewhat different pattern of
data access.
Compressed Column Storage

Analogous to CRS, there is compressed column storage (CCS), which is also called the Harwell-
Boeing sparse matrix format. The CCS format is identical to the CRS format except that the
columns of A are stored (traversed) instead of the rows. In other words, the CCS format is the
CRS format for A .
T

LOVELY PROFESSIONAL UNIVERSITY 83