百度百科:在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 简单来说,稀疏矩阵就是绝大部分都是0的矩阵 ,只包含很少的非零值.
比如,
上述稀疏矩阵非零元素有9个,26个零值.稀疏性是74%.
稀疏矩阵因为绝大部分都是0元素,如果我们仍然按照普通方式存储,无疑会 浪费很多空间 ;同时如果进行运算时,0元素对最终结果也没有帮助, 增加了许多无效计算 . 因此,我们需要设计出新的存储方式,或者说数据结构来存储稀疏矩阵.比较常见的有:
对于稀疏矩阵的存储,为了达到压缩的目的(节省存储空间),只存储非0元素值,但是也要保留非零元素的位置,方便恢复.所以,我们存储时不仅存储非零元素值,同时存储其坐标位置(row,column). 针对这两者的存储,会出现不同的设计方案.这里主要介绍COO,CSR和CSC存储格式.
我们使用三个数组row,column和data分别用来存储非零元素坐标的row_index,col_index,以及数值.比如:
NNO:The number of nonzero.矩阵非零元素个数. 三个数组的长度都是NNO.data[i]在原稀疏矩阵中的坐标为(row[i],col[i]]).
可以发现,这种存储方式中,row数组和column数组中有一定的重复元素.我们是否可以针对这个冗余特性进一步进行压缩?之后出现CSR,CSC,分别是对row数组和column数组进行了压缩.
对COO稀疏矩阵存储格式的三个数组中的row数组进行压缩.其他两个数组保持不变;三个数组分别是row_ptr,columns和data.其中columns和data数组长度均为NNO(矩阵的非零元素个数). 如何对COO的row进行压缩?
row_ptr存储的是每行的第一个非零元素距离稀疏矩阵第一个元素的偏移位置;
由row_ptr我们可以知道每行非零元素在data中的index范围.第i行的非零元素为data[row_ptr[i]:row_ptr[i+1]],对data数组的切片,不包含data[row_ptr[i+1]];同时第i行非零元素的col坐标分别为columns[row_ptr[i]:row_ptr[i+1]];对data和columns的访问相似,index是相同的.
如上图中,第0行非零元素在data中是data[0:2],就是1,7;列坐标为columns[0:2],就是0,1,第1行非零元素为data[2:4],有两个元素2和8,列坐标分别为columns[2:4],1和2.
方便进行行操作.
和CSR类似.只不过对列进行压缩,row和data保持不变.
方便进行列操作.
