**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)

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

.