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, but 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 [132], which, unlike compressed diagonal storage (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
val(:,-1) | 0 | 3 | 7 | 8 | 9 | 2 | ||||
val(:, 0) | 10 | 9 | 8 | 7 | 9 | -1 | ||||
val(:,+1) | -3 | 6 | 7 | 5 | 13 | 0 |