Page 91 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The CCS format is specified by the 3 arrays {val, row_ind, col_ptr}, where row_ind stores the
row indices of each non-zero, and col_ptr stores the index of the elements in val which start a
column of A.

Example: The CCS format for the matrix A is given by

Figure 6.6: CCS Format for the Matrix Given in Figure 6.4

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

row_ind 1 2 4 2 3 5 6 3 4 5 6 2 5 6

col_ptr 1 4 8 10 13 17 20

Block Compressed Row Storage

If the sparse matrix A is composed of square dense blocks of non-zeros in some regular pattern,
we can modify the CRS (or CCS) format to exploit such block patterns. Block matrices typically
arise from the discretization of partial differential equations in which there are several degrees
of freedom associated with a grid point. We then partition the matrix in small blocks with a size
equal to the number of degrees of freedom and treat each block as a dense matrix, even though
it may have some zeros.

If n is the dimension of each block and nnzb is the number of non-zero blocks in the n × n matrix
b
2
A, then the total storage needed is nnz = nnzb × n . The block dimension n of A is then defined
b d
by n = n/n .
d b
Similar to the CRS format, we require three arrays for the BCRS format: a rectangular array
for floating point numbers (val(1 : nnzb, 1 : n 1 : n ,)) which stores the non-zero blocks in (block)
b b
row-wise fashion, an integer array (col_ind(1 : nnzb)) which stores the actual column
indices in the original matrix A of the (1, 1) elements of the non-zero blocks, and a pointer array
(row_blk(1 : n + 1)) whose entries point to the beginning of each block row in val(:,:,:) and
d
col_ind(:).
!

Caution The savings in storage locations and reduction in time spent doing indirect
addressing for block compressed row storage (BCRS) over CRS can be significant for
matrices with a large n .
b
Compressed Diagonal Storage

If the matrix A is banded with bandwidth that is fairly constant from row to row, then it is
worthwhile to take advantage of this structure in the storage scheme by storing subdiagonals of
the matrix in consecutive locations. Not only can we eliminate the vector identifying the column
and row, but we can pack the non-zero elements in such a way as to make the matrix-vector
product more efficient. This storage scheme is particularly useful if the matrix arises from a
finite element or finite difference discretization on a tensor product grid.

84 LOVELY PROFESSIONAL UNIVERSITY