稀疏矩阵存储格式 - お前はどこまで見えている

1. 简介

稀疏矩阵是指矩阵中大多数元素为 $0$ 的矩阵。多数情况下，实际问题中的大规模矩阵基本上都是稀疏矩阵，而且很多稀疏矩阵的稀疏度在 $90\%$ 甚至 $99\%$ 以上。

2. 存储格式

相较于一般的矩阵存储格式，即保存矩阵所有元素，稀疏矩阵由于其高度的稀疏性，因此需要更高效的存储格式。

2.1 Coordinate(COO)

每个非 $0$ 元素使用一个三元组来表示——(行号,列号,数值)。实际存储分三个数组存储，分别表示行索引、列索引、数值。这种格式最简单，每个三元组自己可以定位，空间效率不是最优。

2.2 Compressed Sparse Row(CSR)

CSR 格式是比较标准的一种格式，其同样需要三类数据来表示——数值、列号、行偏移。CSR 不是三元组，而是整体的编码方式。其中，数值和列号和 COO 格式中的一致，某一行的行偏移表示该行的第一个元素在数值数组中的索引。实际存储分三个数组存储，分别表示数值、列号、行偏移。

2.3 ELLPACK(ELL)

【注】上图中间矩阵有误，第三行应为 0 2 3。

ELL 格式用两个和原始矩阵相同行数的矩阵来分别存储列号和数值，行号用自身所在的行来表示。这两个矩阵每一行都是从头开始放，如果没有元素了就用标志符号 * 结束。

如果原稀疏矩阵某一行有很多元素，那么这两个矩阵就会很宽，其他行结尾的 * 标志很多，浪费存储空间。一种解决方法是存成数组：

1 2	`0 1 * 1 2 * 0 2 3 * 1 3 * 1 7 * 2 8 * 5 3 9 * 6 4 *`

但这样要取一行就不太方便。

2.4 Diagonal(DIA)

DIA 格式沿原稀疏矩阵对角线来存储，省略全零的对角线，存储矩阵的列代表对角线，行代表行。对角线从左下往右上开始，行对应原矩阵行存储。

DIA 格式对于对角性很好的矩阵的压缩率很高，但对角性不好的就比较糟糕。

2.5 Hybrid(HYB)

HYB = ELL + COO 格式主要是为了解决 ELL 的问题。HYB 格式是对 ELL 格式的一种修正，如果原稀疏矩阵中某一行特别多，造成其他行的浪费，就把这些多出来的元素用 COO 单独存储。

3. 对比

3.1 优缺点概述

存储格式	优点	缺点
COO	灵活、简单	压缩、稀疏矩阵矢量乘积效率低
CSR	灵活、简单	稀疏矩阵矢量乘积效率低
ELL	稀疏矩阵矢量乘积效率高	压缩效率不稳定
DIA	稀疏矩阵矢量乘积效率高	压缩效率不稳定

COO 格式常用于从文件中进行稀疏矩阵的读写，而 CSR 格式常用于读入数据后进行稀疏矩阵的计算。

3.2 存储效率

CSR 格式在存储稀疏矩阵时非零元素平均使用的字节数最为稳定；DIA 格式存储稀疏矩阵时非零元素平均使用的字节数与矩阵类型关联较大，该格式更适合 Structured Mesh 结构的稀疏矩阵，对于 Unstructured Mesh 和 Random Matrix，DIA 格式使用的字节数是 CSR 的十几倍。