锯齿对角存储格式

锯齿对角存储（JDS）格式在并行和向量处理器上实现迭代方法时非常有用（参见Saad [385]）。与CDS格式类似，它提供的向量长度基本上与矩阵大小相同。 它在牺牲收集/分散操作的情况下，比CDS格式更节省空间。

一种简化的JDS形式，称为ITPACK存储或普渡存储，可以描述如下。对于以下非对称矩阵，所有元素都向左移动：

\left[\begin{array}{rrrrrr} 10 & -3 & 0 & 1 & 0 & 0 \\ 0 & 9 & 6 & 0 & -2 & 0 \\ 3 & 0 & 8 & 7 & 0 & 0 \\ 0 & 6 & 0 & 7 & 5 & 4 \\ 0 & 0 & 0 & 0 & 9 & 13 \\ 0 & 0 & 0 & 0 & 5 & -1 \end{array}\right] \rightarrow \left[\begin{array}{rrrr} 10 & -3 & 1 & \\ 9 & 6 & -2 & \\ 3 & 8 & 7 & \\ 6 & 7 & 5 & 4 \\ 9 & 13 \\ 5 & -1 \end{array}\right]

之后，列被连续存储。所有行都在右侧用零填充，以使它们具有相同的长度。对应于矩阵元素数组val(:,:)，还存储了一个列索引数组col_ind(:,:)：

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

col_ind(:, 1)	1	2	1	2	5	5
col_ind(:, 2)	2	3	3	4	6	6
col_ind(:, 3)	4	5	4	5	0	0
col_ind(:, 4)	0	0	0	6	0	0

显然，这种结构中的填充零可能是一个缺点，特别是当矩阵的带宽变化很大时。因此，在CRS格式中，我们根据每行的非零元素数量按降序重新排序矩阵的行。压缩和置换的对角线随后存储在一个线性数组中。这种新的数据结构称为锯齿对角线。

具体来说，我们存储来自每行的val, col_ind中的所有第一个（密集）向量元素，以及包含相应元素列索引的整数向量。接下来是来自左侧第二个位置的元素组成的第二条锯齿对角线。我们继续构建越来越多的这些锯齿对角线（其长度逐渐减小）。

锯齿对角线的数量等于第一行中的非零元素数量，即矩阵A中任何行中非零元素的最大数量。因此，表示n \times n矩阵A的数据结构包括一个重新排序行的置换数组（perm(1:n）），一个包含连续锯齿对角线的浮点数组（jdiag(:)），一个包含相应列索引的整数数组（col_ind(:)），最后是一个指针数组（jd_ptr(:)），其元素指向每个锯齿对角线的起始位置。Saad在[385]中讨论了JDS在矩阵乘法中的优势。

上述矩阵A在使用线性数组{perm, jdiag, col_ind, jd_ptr}的JDS格式如下（锯齿对角线用分号分隔）：

jdiag	1	3	7	8	10	2;	9	9	8 \cdots -1;	9	6	7	5;	13
col_ind	1	1	2	3	1	5;	4	2	3 \cdots 6;	5	3	4	5;	6

perm

5

2

3

4

1

6

jd_ptr

1

7

13

17

 .