稀疏矩阵汇总

  稀疏矩阵的数据结构有很多种，每种数据结构都有它的优点，本文中列举了目前主流的稀疏结构并分析了其特点。稀疏矩阵的存储涉及到多种数据结构的设计与选择，目前流行的稀疏数据结构包括 COO（Coordinate）、CSR（Compressed Sparse Row）、CSC（Compressed Sparse Column）、LIL（Row-based List of Lists）、DIA（DIAgonal storage）、BSR（Block Sparse Row）、ELL（ELLPACK）等。COO 格式通过使用三个数组来分别表示非零元素的坐标和值，适用于具有 任意分布 的非零元素的稀疏矩阵；CSR 和 CSC 格式则分别以行和列为主导，使用压缩行和压缩列的方式存储非零元素，适合于 以行或列为基础 的操作，如矩阵向量乘法和 LU 分解；LIL 格式通过链表的方式按行存储非零元素，提供了灵活的 插入 和修改 操作；DIA 格式则仅存储对角线元素和每个对角线的偏移量，实现了压缩存储；BSR 提供了良好的 分块 特性；ELL 格式则将非零元素对齐存储在二维数组中，具有高效的空间和访问效率。

  在选择稀疏矩阵的数据结构时，应综合考虑应用场景和需求。不同的数据结构在不同矩阵规模下可能呈现不同的特性和效率。因此，深入了解各种数据结构的优势和限制，根据实际情况选择合适的数据结构至关重要。这样可以确保在稀疏矩阵的存储、操作和计算过程中获得最佳的性能和效率。

相关知识补充：

下文中会多次提到稀疏矩阵的 向量内积（SpMV，Sparse Matrix-vector Product）操作，在此强调定义并复习一下其具体的过程。假设 $A \in \mathbb{R}^{m \times n}$，以及 $x \in \mathbb{R}^{n}$，$y=Ax$ 即为 SpMV 运算，其计算结果是一个长度为 $m$ 的向量，按照正常的稠密矩阵的算法需要进行 $mn^2$ 次乘法，且需要 $x$ 中的每个元素都需要被重复检索 $m$ 次。

• 若 $A$ 是一个 CSR 格式的稀疏矩阵，我们只需要计算矩阵 $A$ 中非零元所在行即可；
• 若 $A$ 是一个 CSC 格式的稀疏矩阵，我们只需要检索矩阵 $A$ 中非零元所在列索引对应的 $x[i]$ 即可；
• 若 $A$ 是一个 ELL 格式的稀疏矩阵，其使用两个矩阵分别存储非零元素的列索引和对应的数值。在进行 SpMV 运算时，ELL 格式可以通过并行计算同时访问每一行的非零元素和对应的向量元素，减少了数据依赖性，提高了计算效率。

COO，Coordinate

  COO（Coordinate）通过使用三个数组来表示矩阵的非零元素的坐标和对应的值，从而实现高效的存储和操作。其中，数组 row 存储行坐标，数组 col 存储列坐标，数组 data 存储对应的值。COO 格式适用于具有 任意分布 的非零元素的稀疏矩阵，但在稀疏性较高且需要频繁访问的情况下可能效率较低，因为元素的访问需要通过遍历数组来找到特定位置的元素。

• row：行索引数组
• col：列索引数组
• data：数据数组

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

将上述矩阵 $A$ 转换成 COO 格式，结果如下所示：

性质

优点

• 可以高效转换成其他稀疏矩阵的结构。

缺点

• 不能直接进行算数运算和行列切片。

CSR，Compress Sparse Row

  CSR 是在 COO 的基础上将行进行压缩，它通过将矩阵的行存储为一组压缩行，并使用两个数组来表示非零元素的 值和对应的 列索引 ，从而实现高效的存储和操作。该格式在处理稀疏矩阵时具有较高的空间效率和访问效率，特别 适用于以行为主导的操作，如矩阵向量乘法和稀疏矩阵的求解。

• indptr：行指针偏移数组
• indices：列索引数组
• data：数据数组

属性的特征：

• 矩阵行数 = indptr 数组的长度 - 1
• 矩阵列数 = indices 数组中最大的元素数值 + 1
• indices 和 data 的数组长度相同，且其长度即为 nnz

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

  将上述矩阵 $A$ 转换成 CSR 格式，结果如下所示。CSR 的数值数组 data 和列索引数组 indices 与 COO 格式的表示一致，行指针偏移数组表示每一行的第一个元素在 data 数组中的起始偏移位置，即前面每行包含的非零元素个数的总和。如下所示的 indptr：

• row[0]： 因为第一行的非零元素是矩阵中的第一个非零元素，所以是 0 偏移，即indptr[0]=0；
• row[1]： 第二行元素的前面已经有了第一行的 3 个非零元素，所以是 3 偏移，即indptr[1]=3；
• row[2]： 因为第二行没有非零元素，所以第三行的偏移量没有增加，依然是 3 偏移，即indptr[2]=3；
• 最后，在行指针偏移数组 indptr 的末尾补上矩阵的总非零元素个数作为总偏移量，本例中是 6。

性质

优点

• 可以高效计算 CSR 之间的加法和乘法；
• 可以高效进行 SpMV 运算；
• 可以高效进行的行切片。

缺点

• 列切片操作较慢（列切片考虑 CSC）；
• 转换成其他稀疏矩阵的结构时效率较低（可以考虑 LIL 或 DOK）。

CSC，Compressed Sparse Column

  CSC（Compressed Sparse Column）和 CSR 的原理相同，只是矩阵按列压缩存储。它通过将矩阵的列存储为一组压缩列，并使用两个数组来表示非零元素的 值和对应的 行索引，从而实现高效的存储和操作。该格式在处理稀疏矩阵时具有较高的空间效率和访问效率，特别适用于以列为主导的操作，如矩阵向量乘法和 LU 分解。

• indptr：列指针偏移数组
• indices：行索引数组
• data：数据数组

属性的特征：

• CSC 和 CSR 的表示互为转置，即矩阵 $A$ 的 CSC 表示就是矩阵 $A^T$ 的 CSR 表示；
• 矩阵列数 = indptr 数组的长度 - 1 ；
• 矩阵行数 = indices 数组中最大的元素数值 + 1 ；
• indices 和 data 的数组长度相同，且其长度即为 nnz 。

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

  将上述矩阵 $A$ 转换成 CSC 格式，结果如下所示。CSC 的转换和 CSR 的原理相同，只是从按行压缩转换成了按列压缩存储。如下所示：

• col[0]： 第一列的第一个非零元素 A[0,0]=1 是 0 偏移，且行索引为 0，即 indptr[0]=0，indices[0]=0；第一列的第二个非零元素 A[2,0]=4，行索引为 2，即 indices[1]=2；
• col[1]： 第二列元素的前面已经有了第一列的 2 个非零元素，所以是 2 偏移，即indptr[1]=2；
• col[2]： 因为第二列没有非零元素，所以第三列的偏移量没有增加，依然是 2 偏移，即 indptr[2]=2，而第三列的第一个非零元素 A[0,2]=2 行索引为 0，即 indices[2]=0，以此类推得到非零元素 A[2,2]=5 的行索引为 indices[3]=2；
• col[3]： 第四列的前面已经有了 4 个非零元素，所以偏移量为 4，即 indptr[3]=4，类似得到非零元素 A[0,3]=3 的行索引为 indices[4]=0，非零元素 A[2,3]=6的行索引为 indices[5]=2；
• 最后，在列指针偏移数组 indptr 的末尾补上矩阵的总非零元素个数作为总偏移量，本例中是 6。

性质

优点

• 可以高效计算 CSC 之间的加法和乘法；
• 可以高效进行 SpMV 运算，但是会略差于 CSR 和 BSR；
• 可以高效进行的列切片。

缺点

• 行切片操作较慢（行切片考虑 CSR）；
• 转换成其他稀疏矩阵的结构时效率较低（可以考虑 LIL 或 DOK）。

LIL，Row-based List of Lists sparse

  LIL（Row-based List of Lists sparse）使用 链表 的方式按行存储矩阵的非零元素。每一行都由一个链表表示，链表中的节点存储了非零元素的 值和对应的 列索引。

• rows：行索引数组
• data：数据数组

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

将上述矩阵 $A$ 转换成 LIL 格式，结果如下所示：

性质

优点

• 可以高效转换成其他稀疏矩阵的结构；
• 支持灵活切片；
• 可以灵活使用列表赋值来添加元素。

缺点

• 运算 LIL + LIL 的时候比较慢（可以考虑 CSR 或 CSC）；
• 列切片操作较慢（列切片考虑 CSC）；
• 进行 SpMV 运算操作较慢（可以考虑 CSR/CSC ）；
• 当矩阵很大时，考虑使用 COO。

DIA，DIAgonal storage

  DIA（DIAgonal storage）通过仅存储 对角线元素 和每个对角线的 偏移量 来实现压缩存储。

• data：数据数组，每一行代表对角线，列代表元素所在列；
• offsets：对角线偏移量数组，其存储了每条非零对角线基于主对角线的偏移量，在主对角线下方则为负值，在主对角线上方则为正值。

示例

  将上述矩阵 $A$ 转换成 DIA 格式，结果如下所示，首先将矩阵填充为方阵，从左下向右上遍历对角线。

• 第一条对角线为 0，忽略；
• 第二条对角线为 [4, 0]，记录到 data 数组中，列索引为原所在列，并记录其相对于主对角线的偏移量为 -2；
• 第三条对角线为 [0, 0, 0]，忽略；
• 第四条对角线为 [1, 0, 5, 0]，记录到 data 数组中，因为这是主对角线，所以偏移量为 0；
• 第五条对角线为 [0, 0, 6]，记录到 data 数组中，并记录其相对于主对角线的偏移量为 1；
• 第六条对角线为 [2, 0]，记录到 data 数组中，并记录其相对于主对角线的偏移量为 2；
• 第七条对角线为 [3]，记录到 data 数组中，并记录其相对于主对角线的偏移量为 3。

  DIA 格式的 data 矩阵和 offsets 数组：

  由此例可见 DIA 并不适合存储不具有强对角性质的矩阵，会因为一些散落在非对角线上的非零元素而浪费过多的空间内存。而下面这个例子同样为 6 个非零元素，使用 DIA 格式存储就十分适合。

  DIA 格式的 data 矩阵和 offsets 数组：

性质

优点

• 适用于存储具有多个对角线的稀疏矩阵。相比于其他稀疏矩阵格式（如 COO、CSR 和 CSC），DIA 格式通常需要更少的存储空间。

缺点

• 对于非对角线上的元素需要较大的多余存储空间，和较高的访问代价；
• 因为对角线的长度固定，所以修改比较困难。

MSR，Modified Sparse Row

MSR 是对 CSR 方式的一种改进，其 引入了对角元素的优化机制，对于非对角元素存储的基本想法依然是 CSR。

属性

• diagonal：存储主对角线上的数据数组
• indptr：行指针偏移数组
• indices：列索引数组
• data：数据数组

示例

  首先将矩阵 $A$ 中的主对角线提取出来，并存储在 diagonal 数组中。然后将剩下的部分使用 CSR 的格式进行存储，如下所示：

性质

  MSR 相比 CSR 在存储上更加紧凑，可以节省存储空间。

BSR，Block Sparse Row

  BSR（Block Sparse Row）是一种用于特殊稀疏矩阵的存储方式。这类矩阵的特点是矩阵可以均匀分块，并且非零矩阵元素恰好位于某些块上。BSR 格式可以通过类似于 CSR 格式的方式对矩阵进行压缩存储，不同之处在于存储的不再是单个矩阵元素，而是矩阵的一个子块。

• indptr：行指针偏移数组
• indices：列索引数组
• data：数据数组
• blocksize (R, C)：其中的 R 和 C 分别代表分块矩阵的行和列，其需要满足被原矩阵的行和列整除。

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

  将上述矩阵 $A$ 转换成 BSR 格式，结果如下所示。BSR 的转化方式和 CSR 一样，又因为矩阵$A$ 不具有局部块，所以 blocksize=(1, 1)，indptr、indices 和 data 均与 CSR 格式的结果完全一样。

  如果把 blocksize 改成 (2, 2) 其他的均不变，则表示的是一个扩大后的 A 矩阵，如下所示：

$A = \left[\begin{array}{llllllll} \mathbf{1} & \mathbf{1} & \color{lightgray}0 & \color{lightgray}0 & \mathbf{2} & \mathbf{2} & \mathbf{3} & \mathbf{3}\\ \mathbf{1} & \mathbf{1} & \color{lightgray}0 & \color{lightgray}0 & \mathbf{2} & \mathbf{2} & \mathbf{3} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \mathbf{4} & \color{lightgray}0 & \color{lightgray}0 & \mathbf{5} & \mathbf{5} & \mathbf{6} & \mathbf{6}\\ \mathbf{4} & \mathbf{4} & \color{lightgray}0 & \color{lightgray}0 & \mathbf{5} & \mathbf{5} & \mathbf{6} & \mathbf{6}\\ \end{array}\right]$

性质

优点

• 具有良好的数据局部性。

缺点

• 适用范围有限。

ELL，ELLPACK

  ELL（ELLPACK）是一种用于稀疏矩阵存储和操作的格式，它通过将非零元素按行对齐存储在一个二维数组中，同时在每行中保留对应的列索引，实现高效的空间和访问效率。

• indices：列索引矩阵
• data：数据矩阵

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

  ELL 使用两个与原始矩阵具有相同行数的矩阵来存储稀疏矩阵，其中第一个矩阵（列索引矩阵indices ）存储列号，第二个矩阵（数值矩阵 data ）存储数值。行号则通过矩阵的行号来表示。这两个矩阵的每一行都按照从头开始的顺序存放元素，如果没有元素，则使用特定的标志（例如 *）来表示结束。

indices：

data：

性质

优点

• 适用于存储具有相对较小非零元素数量的稀疏矩阵。相比于传统的稀疏矩阵存储格式（如 COO、CSR 和 CSC），ELL 格式通常需要更少的存储空间；
• 可以高效进行 SpMV 运算；
• 具有高效的行访问性能。

缺点

• 因为行数是固定的，所以修改较为困难。

Hybrid（ELL + COO）混合存储

  为了解决 ELL 中某一行特别多，造成其他行的浪费，那么把这些多出来的元素用 COO 单独存储。

ELL 部分：

• indices：列索引矩阵
• data_ell：数据矩阵

COO 部分：

• row：行索引数组
• col：列索引数组
• data_coo：数据数组

示例

$A = \left[\begin{array}{llll} \mathbf{1} & \color{lightgray}0 & \mathbf{2} & \mathbf{3}\\ \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0 & \color{lightgray}0\\ \mathbf{4} & \color{lightgray}0 & \mathbf{5} & \mathbf{6}\\ \end{array}\right]$

  因为第三行的非零元素比其它行多一个，若使用纯 ELL 格式会造成其他行的空间浪费，因此对于多出来的非零元素使用 COO 格式进行单独存储。

ELL 部分：
indices：

data_ell：

COO 部分：

性质

  Hybrid 混合存储提供了灵活性，可以根据矩阵的特性和需求来选择适合的子格式。

总结与比较

• DIA 和 ELL 格式在进行 SpMV 运算时效率最高，所以它们是应用迭代法（如共轭梯度法）解稀疏线性系统最快的格式；
• COO 和 CSR 格式比起 DIA 和 ELL 来，更加灵活，易于操作；
• ELL 的优点是快速，而 COO 优点是灵活，二者结合后的 Hybrid 格式是一种不错的稀疏矩阵表示格式；
• CSR 格式的压缩率最为稳定，而 DIA 格式与矩阵类型有较大关系（对角矩阵与随机矩阵之间相差数十倍）。

一些特殊类型矩阵的存储效率

（数值越小说明压缩率越高，即存储效率越高）

• Structured Mesh 结构网格

• Unstructured Mesh 非结构网格

• Random matrix 随机矩阵

• Power-Law Graph 幂律图

格式适用性：

参考来源

• NathanBell1-10-1000.pdf (bu.edu)
• IterMethBook_2ndEd.pdf (umn.edu)
• 稀疏系统 | 算法和数据结构 | 滑铁卢大学 (uwaterloo.ca)
• 稀疏矩阵存储格式总结 + 存储效率对比:COO,CSR,DIA,ELL,HYB_stark_summer 的博客 -CSDN 博客
• Sparse 稀疏矩阵主要存储格式总结 - 知乎 (zhihu.com)