Previous: Block Compressed Row Storage (BCRS)
Up: Survey of Sparse Matrix Storage Formats
Next: Jagged Diagonal Storage (JDS)
Previous Page: Block Compressed Row Storage (BCRS)
Next Page: Jagged Diagonal Storage (JDS)

Compressed Diagonal Storage (CDS)

If the matrix 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, we can pack the nonzero 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.

We say that the matrix is banded if there are nonnegative constants , , called the left and right halfbandwidth, such that only if . In this case, we can allocate for the matrix an array val(1:n,-p:q). The declaration with reversed dimensions (-p:q,n) corresponds to the LINPACK band format [70], which unlike CDS, does not allow for an efficiently vectorizable matrix-vector multiplication if is small.

Usually, band formats involve storing some zeros. The CDS format may even contain some array elements that do not correspond to matrix elements at all. Consider the nonsymmetric matrix defined by

Using the CDS format, we store this matrix in an array of dimension (6,-1:1) using the mapping

Hence, the rows of the val(:,:) array are

.

Notice the two zeros corresponding to non-existing matrix elements.

A generalization of the CDS format more suitable for manipulating general sparse matrices on vector supercomputers is discussed by Melhem in [151]. This variant of CDS uses a stripe data structure to store the matrix . This structure is more efficient in storage in the case of varying bandwidth, but it makes the matrix-vector product slightly more expensive, as it involves a gather operation.

As defined in [151], a stripe in the matrix is a set of positions , where and is a strictly increasing function. Specifically, if and are in , then When computing the matrix-vector product using stripes, each element of in stripe is multiplied with both and and these products are accumulated in and , respectively. For the nonsymmetric matrix defined by

the stripes of the matrix stored in the rows of the val(:,:) array would be

.