稀疏矩阵是指矩阵中的元素大部分是0的矩阵，实际问题中大规模矩阵基本上都是稀疏矩阵，很多稀疏度在90%甚至99%以上,大规模的稀疏造成了大量无效数据的计算和存储资源占用，也无法有效的载入有限内存计算。因此我们需要有高效的稀疏矩阵存储格式。本文总结几种典型的格式：COO,CSR,DIA,ELL,HYB,HASH,BSR。

COO

  • 采用三元组(row, col, data)(或称为ijv format)的形式来存储矩阵中非零元素的信息
  • 三个数组 row 、col 和 data 分别保存非零元素的行下标、列下标与值（一般长度相同）
  • 故 coo[row[k]][col[k]] = data[k] ，即矩阵的第 row[k] 行、第 col[k] 列的值为 data[k]
适用场景
  • 主要用来创建矩阵，因为coo_matrix无法对矩阵的元素进行增删改等操作
  • 一旦创建之后，除了将之转换成其它格式的矩阵，几乎无法对其做任何操作和矩阵运算
①优点
  • 转换成其它存储格式很快捷简便（tobsr()、tocsr()、to_csc()、to_dia()、to_dok()、to_lil()）
  • 能与CSR / CSC格式的快速转换
  • 允许重复的索引（例如在1行1列处存了值2.0，又在1行1列处存了值3.0，则转换成其它矩阵时就是2.0+3.0=5.0）
②缺点
  • 不支持切片和算术运算操作
  • 如果稀疏矩阵仅包含非0元素的对角线，则对角存储格式(DIA)可以减少非0元素定位的信息量
  • 这种存储格式对有限元素或者有限差分离散化的矩阵尤其有效

CSR

  • csr_matrix是按行对矩阵进行压缩的
  • 通过 columu indices, row offset，value来确定矩阵。
  • value表示矩阵中的非零数据
  • 对于第 i 行而言，该行中非零元素的列索引为 indices[indptr[i]:indptr[i+1]]
  • 可以将 columu indptr 理解成利用其自身索引 i 来指向第 i 行元素的列索引
  • 根据[indptr[i]:indptr[i+1]]，我就得到了该行中的非零元素个数，如
    • 若 row_offset[i] = 3 且 row_offset[i+1] = 3 ，则第 i 行的没有非零元素
    • 若 row_offset[j] = 6 且 row_offset[j+1] = 7 ，则第 j 行的非零元素的列索引为 indices[6:7]
  • 得到了行索引、列索引，相应的数据存放在： data[indptr[i]:indptr[i+1]]
适用场景
  • 常用于读入数据后进行稀疏矩阵计算，运算高效
①优点
  • 高效的稀疏矩阵算术运算
  • 高效的行切片
  • 快速地矩阵矢量积运算
②缺点
  • 较慢地列切片操作（可以考虑CSC）
  • 转换到稀疏结构代价较高（可以考虑LIL，DOK）
改进（BCSR、CSC）

注意到其中规则：若 row_offset[i] == row_offset[i+1] ，则第 i 行的全为0元素。由于稀疏矩阵可能连续多行为全0元素行，则CSR的row_offset会有大量稀疏性，则有两种改进：

  • BCSR（双重稀疏行压缩）：可以再新增一个pos数组存row_offset数组中offset数据的所属行，而无需大量的相同offset数据重复。
  • CSC（列压缩）：行压缩转换为列压缩，原理相同

ELL

Linked List Matrix 链表矩阵

  • 使用两个列表存储非0元素data
  • row保存非零元素所在的列
适用场景
  • 适用的场景是逐渐添加矩阵的元素（且能快速获取行相关的数据）
  • 需要注意的是，该方法插入一个元素最坏情况下可能导致线性时间的代价，所以要确保对每个元素的索引进行预排序
①优点
  • 适合递增的构建成矩阵
  • 转换成其它存储方式很高效
  • 支持灵活的切片
②缺点
  • 当矩阵很大时，考虑用coo
  • 算术操作，列切片，矩阵向量内积操作慢

HYB

如果某一行特别多，造成其他行的浪费，那么把这些多出来的元素（比如第三行的9，其他每一行最大都是2个元素）用COO单独存储。

DIA

Diagonal Matrix 对角存储格式

  • 最适合对角矩阵的存储方式
  • dia_matrix通过两个数组确定： data 和 offsets
  • data ：对角线元素的值
  • offsets ：第 i 个 offsets 是当前第 i 个对角线和主对角线的距离
  • data[k:] 存储了 offsets[k] 对应的对角线的全部元素

HASH (dok_matrix)

Dictionary of Keys Matrix 按键字典矩阵

  • 采用字典来记录矩阵中不为0的元素
  • 字典的 key 存的是记录元素的位置信息的元组， value 是记录元素的具体值

适用于逐渐添加矩阵的元素。

①优点

  • 对于递增的构建稀疏矩阵很高效，比如定义该矩阵后，想进行每行每列更新值，可用该矩阵。
  • 可以高效访问单个元素，只需要O(1)

②缺点

  • 不允许重复索引（coo中适用），但可以很高效的转换成coo后进行重复索引
代码示例
dok = sparse.dok_matrix((5, 5), dtype=np.float32)for i in range(5):for j in range(5):dok[i,j] = i+j# 更新元素# zero elements are accessibledok[(0, 0)]# = 0dok.keys() # {(0, 0), ..., (4, 4)}dok.toarray()'''[[0. 1. 2. 3. 4.] [1. 2. 3. 4. 5.] [2. 3. 4. 5. 6.] [3. 4. 5. 6. 7.] [4. 5. 6. 7. 8.]] '''

BSR

  • 基于行的块压缩，与csr类似，都是通过data，indices，row_offset来确定矩阵
  • 与csr相比，只是data中的元数据由0维的数变为了一个矩阵（块），其余完全相同
  • 块大小 blocksize
    • 块大小 (R, C) 必须均匀划分矩阵 (M, N) 的形状。
    • R和C必须满足关系：M % R = 0 和 N % C = 0
    • 适用场景及优点参考csr
  • 也可以用块压缩组合COO

参考：

https://www.cnblogs.com/xbinworld/p/4273506.html

https://zhuanlan.zhihu.com/p/188700729