稀疏矩阵压缩存储:CSR/CSC (Compress Sparse Row/Column)

发布网友发布时间：2023-01-02 13:15

共1个回答

热心网友时间：2023-10-09 15:41

假设有一非对称矩阵A，用CSR表示需要三个向量： val , col_ind , row_ptr 。表示的意义为：

, then
, then

并约定：，其中，为A中非零值的个数

它的CSR表示为：

特别说明一下 row_ptr 的表示含义：
如 row_ptr[2]=3 ，表明矩阵A中第二行（从左至右）的第一个非零值是A中所有非零值的第3个； row_ptr[5]=13 ，表明矩阵A中第五行（从左至右）的第一个非零值是A中所有非零值的第13个； row_ptr[7]=20 指示A中非零值nnz的个数：nnz=20-1=19。

更新CSC的介绍：它的基本思想和CSR完全相同，可以看作CSR的转置，因此这里仅对CSC进行简单的举例介绍。以Song Han的EIE论文为例，PE应存储的weight矩阵为（相同颜色的对应一个PE）：

这一矩阵的采用CSC表示为：

解释”：和上面的CSR表示不同，这里的索引从0开始（上面的CSR举例从1开始，当然也可以从0开始）。index对应的是非零值所在行的index，而pointer指示原始矩阵中每列非零值的数量，pointer的最后一位指示矩阵中非零值的个数。
如 pointer[1]=3 ，表明第二列之前（第一列）含三个非零值，第二列（由上至下）第一个非零值应是所有非零值中的第四个； pointer[2]=4 ，表明第三列之前有四个非零值，第三列（由上至下）第一个非零值应是所有非零值中的第五个； pointer[3] 和 pointer[4] 相等，表明第四列没有非零值；最后， pointer[8]=13 ，表示weight矩阵*有13个非零值。
需要注意的是，这里的Row index是相对的，即相对前一个非零值或第一行的index，上面的CSR中的Column index是绝对的。可根据实际要求选择绝对或相对表示。