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 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 $A=(a_{i,j})$ is banded if there are nonnegative constants $p$, $q$, called the left and right halfbandwidth, such that $a_{i,j}\not=0$ only if  $i-p\leq j\leq i+q$. In this case, we can allocate for the matrix $A$ 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 ${\tt p}+{\tt q}$ 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 $A$ defined by

$$A = \left[\begin{array}{rrrrrr} 10 & -3 & 0 & 0 & 0 & 0 \\ ... ... 9 & 9 & 13 \\ 0 & 0 & 0 & 0 & 2 & -1 \end{array}\right] ~.$$ (270)

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

$${\tt val(i,j)}=a_{i,i+j}.$$ (271)

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

val(:,-1)	0	3	7	8	9	2
val(:, 0)	10	9	8	7	9	-1
val(:,+1)	-3	6	7	5	13	0

Notice the two zeros corresponding to nonexisting matrix elements.