22.1.1 稀疏矩阵的存储¶

严格来说，用户并不一定要理解稀疏矩阵的存储方式。然而，了解这一点有助于理解稀疏矩阵的大小。对于那些希望编写自己的 oct 文件的用户来说，掌握存储技术也是必要的。

存储稀疏矩阵数据的方法有很多种。所有这些方法的共同点是：它们都试图利用对待解决问题的先验知识来降低复杂度和存储需求。Saad 对现有稀疏矩阵存储技术做了很好的总结⁸。对于稠密矩阵，矩阵中某个元素的位置信息隐含在其计算机内存地址中。然而，稀疏矩阵并非如此——矩阵中非零元素的位置信息也必须一并存储。

一种直观的做法是将矩阵元素存储为三元组：其中两个元素表示该元素在数组中的位置（行和列），第三个元素则是数据本身。这种思路在概念上易于理解，但所需的存储空间超出了实际需要。

Octave 采用的存储技术是压缩列格式（Compressed Column Format），类似于耶鲁格式（Yale format）。⁹在这种格式中，每个元素在行中的位置和数据仍然按之前的方式存储。但是，如果我们假设同一列中的所有元素在计算机内存中连续存放，那么只需存储每列中非零元素的个数，而无需存储它们的行位置。因此，假设矩阵中的非零元素数多于列数，就可以在内存使用量上获得优势。

实际上，列索引向量（cidx）的元素个数比列数多一，且第一个元素始终为零。这样做的好处是简化了代码实现，因为不需要对第一列或最后一列做特殊处理。以下是一个简短的 C 语言示例：

  for (j = 0; j < nc; j++)
    for (i = cidx(j); i < cidx(j+1); i++)
       printf ("nonzero element (%i,%i) is %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 和 data，分别表示列索引、行索引和数据。对于上述矩阵，这三个向量的内容如下：

  cidx = [0, 1, 2, 2, 4]
  ridx = [0, 0, 1, 2]
  data = [1, 2, 3, 4]

需要注意的是，上述表示假设第一行和第一列从零开始索引，而在 Octave 中，行和列的索引从 1 开始。因此，第 i 列的元素个数由下式给出：cidx(i + 1) - cidx(i)。

尽管 Octave 使用压缩列格式，但同理也存在压缩行格式。然而，在涉及稀疏矩阵与稠密矩阵的混合运算时，让稀疏矩阵的元素排列顺序与稠密矩阵保持一致是合理的。Octave 以列主序（column-major order）存储稠密矩阵，因此稀疏矩阵也采用同样的方式存储。

Octave 对稀疏矩阵存储还有一个额外的约束：每行中的所有元素必须按行索引递增的顺序存储，这有助于加速某些操作。然而，这意味着在创建稀疏矩阵时必须对元素进行排序。允许元素无序可能在某些方面带来优势，例如使两个稀疏矩阵的连接操作更加简单和快速，但它会在其他地方增加复杂度和降低性能。