压缩对角存储

如果矩阵 A 的带宽在各行之间相当恒定，那么通过在连续位置存储矩阵的子对角线来利用这种结构进行存储是值得的。我们不仅可以消除用于标识列和行的向量，还可以将非零元素打包，以提高矩阵向量乘积的效率。这种存储方案对于矩阵来自张量积网格上的有限元或有限差分离散化特别有用。

我们称矩阵 A=(a_{i,j}) 为带状矩阵，如果存在非负常数 p 和 q，分别称为左半带宽和右半带宽，使得 a_{i,j}\neq 0 仅当 i-p\leq j\leq i+q 时成立。在这种情况下，我们可以为矩阵 A 分配一个数组 val(1:n,-p:q)。具有相反维度的声明 (-p:q,n) 对应于 LINPACK 带状格式[132]，与压缩对角存储（CDS）不同，如果 {\tt p}+{\tt q} 很小，它不允许高效的向量化矩阵向量乘法。

通常，带状格式涉及存储一些零。CDS 格式甚至可能包含一些根本不对应于矩阵元素的数组元素。考虑由以下定义的非对称矩阵 A：

A =\left[\begin{array}{rrrrrr} 10 & -3 & 0 & 0 & 0 & 0 \\ 3 & 9 & 6 & 0 & 0 & 0 \\ 0 & 7 & 8 & 7 & 0 & 0 \\ 0 & 0 & 8 & 7 & 5 & 0\\ 0 & 0 & 0 & 9 & 9 & 13 \\ 0 & 0 & 0 & 0 & 2 & -1 \end{array}\right]. \tag{10.2}

使用 CDS 格式，我们将矩阵 A 存储在一个维度为 (6,-1:1) 的数组中，使用以下映射：

{\tt val(i,j)}=a_{i,i+j}. \tag{10.3}

因此，val(:,:) 数组的行是：

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

注意对应于不存在的矩阵元素的两个零。