22.1.1稀疏矩阵的存储¶

严格地说,用户没有必要理解稀疏矩阵是如何存储的。然而,这样的理解将有助于理解稀疏矩阵的大小。对于那些希望创建自己的oct文件的用户来说,理解存储技术也是必要的。

有许多不同的存储稀疏矩阵数据的方法。所有方法的共同点是,在给定将要解决的特定问题类别的先验知识的情况下,它们试图减少复杂性和存储量。Saad很好地总结了现有的存储稀疏矩阵技术⁸对于全矩阵,矩阵中矩阵的元素的点的知识从其在计算机存储器中的位置来暗示。然而,稀疏矩阵的情况并非如此,因此矩阵的非零元素的位置必须相等地存储。

一个明显的方法是存储矩阵的元素,其中两个元素是它们在数组中的位置(行和列),第三个元素是数据本身。这在概念上很容易理解,但需要比严格要求更多的存储空间。

Octave中使用的存储技术是压缩列格式。它类似于耶鲁大学的格式。⁹在这种格式中,行中每个元素的位置和数据都像以前一样存储。然而,如果我们假设同一列中的所有元素都存储在计算机内存中,那么我们只需要存储每列中非零元素的数量信息,而不是它们的位置信息。因此,假设矩阵中的非零元素比矩阵中的列多,我们就赢得了所使用的内存量。

事实上,列索引比列数多包含一个元素,第一个元素始终为零。这样做的优点是简化了代码,因为第一列或最后一列没有特殊情况。一个简短的例子,演示了这一点。

对于(j=0;j<nc;j++)对于(i=cidx(j);i＜cidx(j+1);i++)printf(“非零元素(%i,%i)为%d\n”,ridx(i),j,data(i));

通过考虑上面的例子如何应用于示例矩阵,可以有一个清晰的理解

1   2   0  0    0   0   0  3    0   0   0  4

这个矩阵的非零元素是

(1, 1)  ⇒ 1   (1, 2)  ⇒ 2   (2, 4)  ⇒ 3   (3, 4)  ⇒ 4.

这将被存储为三个向量cidx,ridx和数据,分别表示列索引、行索引和数据。上述矩阵的这三个向量的内容为

  cidx= [0, 1, 2, 2, 4]ridx= [0, 0, 1, 2]数据= [1, 2, 3, 4]

请注意,这是这些元素的表示,假设第一行和第一列从零开始,而在Octave本身中,行和列索引从一开始。因此我-第th列从给出cidx(我1.cidx(我).

尽管Octave使用压缩列格式,但需要注意的是,压缩行格式也是可能的。然而,在混合稀疏矩阵和稠密矩阵之间的混合运算中,稀疏矩阵的元素与稠密矩阵的元素顺序相同是有意义的。Octave将稠密矩阵存储在列主序中,所以稀疏矩阵以这种方式相等地存储。

Octave使用的稀疏矩阵存储的另一个限制是,行中的所有元素都按行索引的升序存储,这使得某些操作更快。然而,在创建稀疏矩阵时,它强制要求对元素进行排序。拥有无序元素是一个潜在的优势,因为它使将两个稀疏矩阵连接在一起的操作变得更容易、更快,尽管它在其他地方增加了复杂性和速度问题。