三种稀疏矩阵：COO,CSR和CSC
郝伟 2021/08/12

稀疏格式储存

在矩阵的表示中，常见的有三种格式：COO，CSR和CSC，含意如下：
COO：Coordinate Format, (rowid, colid, data)
CSR：Compressed Sparse Row, [saprse_rowids], [(colid, data)]
CSC：Compressed Sparse Column, [saprse_colids], [(rowid, data)]

注：在Sparse matrices (scipy.sparse) 定义了7种矩阵，可以参见 https://docs.scipy.org/doc/scipy/reference/sparse.html。

首先给出一个示例矩阵
$M=\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0.2 & 0.5 & 0 \\ 0 & 0 & 0 & 1.2 \\ 0 & 0 & 4.6 & 0 \end{bmatrix}$

在这个矩阵中，共有16个元素，其中4个为非0元素:
$a_{22}=0.2$
$a_{23}=0.5$
$a_{34}=1.2$
$a_{43}=4.6$
如果使用8字节浮点型来表示，那么这个矩阵光元素就需要占用16*8=128个字节。

COO

使用COO的表示方式如下所示：

[(2,2,0.2),
 (2,3,0.5),
 (3,4,1.2),
 (4,3,4.6)]

每个非0元素使用（行号，列号，值）的形式表示，假设行号与列号使用4字节整型表示，那么一个元素占用4+4+8=16个字节，4个元素占用64个字节，相比于原始状态，节点了64个字节。

CSR和CSC

Rows:    [0,0,2,3,4] # 长度为 row_count + 1
Columns: [1,2,3,2]   # 表示每个元素在当前行的列编号，下标从0开始。
Values:  [0.2,0.5,1.2,4.6] # 对应的值

总共需要 54+44+4*8=68个字节

CSC与CSR类似，只不过由用行表示变为用列表示，故省略。

对比

COO和CSR在使用时，对于长度为NxN的矩阵：

当元素个数少于N+1时，COO更省空间；
当元素个数等于N+1时，两者占用空间相同
当元素个数大于N+1时，CSR更省。

总体来说：

CSR优点：高效的CSR + CSR, CSR *CSR算术运算；高效的行切片操作；高效的矩阵内积内积操作。但是列切片操作慢（相比CSC）；稀疏结构的变化代价高（相比LIL 或者 DOK）。CSR格式在存储稀疏矩阵时非零元素平均使用的字节数(Bytes per Nonzero Entry)最为稳定（float类型约为8.5，double类型约为12.5）。CSR格式常用于读入数据后进行稀疏矩阵计算。
原文链接：https://blog.csdn.net/gaoborl/article/details/82869858

scipy的实现

coo_matrix/csr_matrix