① 多维数组-矩阵的压缩存储- 稀疏矩阵（一）
稀疏矩阵
设矩阵A mn 中有s个非零元素 若s远远小于矩阵元素的总数(即s< <m×n)，则称a为稀疏矩阵。 p=""> </m×n)，则称a为稀疏矩阵。>
1、稀疏矩阵的压缩存储
为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零
元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，a ij )，并由此三元组惟一确定。
稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法【参见参考书目】。
2、三元组表
将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序
存储结构称为三元组表。
注意：
以下的讨论中，均假定三元组是按行优先顺序排列的。
【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)
(1)三元组表的类型说明
为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。.WINGwIT.其类型描述为：
#define MaxSize 10000 //由用户定义
typedef int DataType; //由用户定义
typedef struct { //三元组
int i，j;//非零元的行、列号
DataType v; //非零元的值
}TriTupleNode;
typedef struct{ //三元组表
TriTupleNode data[MaxSize]; //三元组表空间
int m,n，t; //矩阵的行数、列数及非零元个数
}TriTupleTable;
(2) 压缩存储结构上矩阵的转置运算
一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
A[i][j]=B[j][i]，0≤i <m，0≤j<n， p=""> </m，0≤j<n，>
即A的行是B的列，A的列是B的行。
【例】下图中的B和上图中的A互为转置矩阵。
①三元组表表示的矩阵转置的思想方法
第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
第二步：当三元组表非空(A矩阵的非零元不为0)时，根据A矩阵三元组表的结点空间data(以下简称为三元组表)，将A的三
元组表a->data置换为B的三元组表b->data。
②三元组表的转置
方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有
列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。具体实现参见
【 动画演示 】
③具体算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩阵A、B的三元组表表示，求A转置为B
int p，q，col;
b->m=a->n; b->n=a->m; //A和B的行列总数互换
b->t=a->t; //非零元总数
if(b->t<=0)
Error("A=0"); //A中无非零元，退出
q=0;
for(col=0;coln;col++) //对A的每一列
for(p=0;pt;p++) //扫描A的三元组表
if(a->data[p].j==col){ //找列号为col的三元组
b->data[q).i=a->data[p].j;
b->data[q].j=a->data[p].i;
b->data[q].v=a->data[p].v;
q++;
}
} //TransMatrix
④算法分析
该算法的时间主要耗费在col和p的二重循环上：
若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。
通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。
由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。
lishixin/Article/program/sjjg/201311/23897
② 稀疏矩阵的存储空间
一个稀疏矩阵中有许多元素等于零,这便于矩阵的计算和保存.如果Matlab把一个矩阵当作稀疏矩阵,那么只需在m×3的矩阵中存储m个非零项.第1列是行下标,第2列是列下标,第3列是非零元素值,不必保存零元素.如果存储一个浮点数要8个字节,存储每个下标要4个字节,那么整个矩阵在内存中存储需要1 6×m个字节.
A = e y e ( 1 0 0 0 ) ;
得到一个1 0 0 0×1 0 0 0的单位矩阵,存储它需要8 MB空间.如果使用命令:
B = s p e y e ( 1 0 0 0 ) ;
用一个1 0 0 0×3的矩阵来代表,每行包含有一个行下标,列下标和元素本身.只需1 6 K B的空间就可以存储1 0 0 0×1 0 0 0的单位矩阵,它只需要满单位矩阵的0 . 2 %存储空间.对于许多的广义矩阵也可这样来作.
③ 稀疏矩阵定义以及存储格式(COO,CSR,CSC)
网络:在矩阵中，若数值为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保持不变.
方便进行列操作.
④ 稀疏矩阵压缩存储：CSR/CSC (Compress Sparse Row/Column)
假设有一非对称 矩阵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是绝对的。 可根据实际要求选择绝对或相对表示。
⑤ 稀疏矩阵的压缩存储只需要存储什么
非零元素。
对于一个用二维数组存储的稀疏矩阵Amn，如果假设存储每个数组元素需要L个字节，那么存储整个矩阵需要m*n*L个字节。但是，这些存储空间的大部分存放的是0元素，从而造成大量的空间浪费。为了节省存储空间，可以只存储其中的非0元素。
(5)稀疏矩阵存储单元扩展阅读
稀疏矩阵算法的最大特点是通过只存储和处理非零元素从而大幅度降低存储空间需求以及计算复杂度，代价则是必须使用专门的稀疏矩阵压缩存储数据结构。稀疏矩阵算法是典型的不规则算法，计算访存比很低，并且计算过程中的访存轨迹与稀疏矩阵的稀疏结构相关。
⑥ 稀疏矩阵一般的压缩存储方法有两种
分别是三元组和十字链表。
三元组是指形如（（x，y），z）的集合（这就是说，三元组是这样的偶，其第一个射影亦是一个偶），常简记为（x，y，z）。
三元组是计算机专业的一门公共基础课程——数据结构里的概念。主要是用来存储稀疏矩阵的一种压缩方式，也叫三元组表。假设以顺序存储结构来表示三元组表（triple table），则得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。
十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。
拓展资料：
十字链表（Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧都有一个结点，对应于每个定顶点也有一个结点。
十字链表之于有向图，类似于邻接表之于无向图。
也可以理解为 将行的单链表和列的单链表结合起来存储稀疏矩阵称为十字链表， 每个节点表示一个非零元素。
三元组解释：
1、所谓“三元组”是指图形的几何元素构成、图线间的拓扑关系和尺寸约束。如果一组图形的前二元相同而只是尺寸大小不同，则这组图形构成一族形状相同的系列化图形。
2、把组成一个元素的三个数称为三元组。一个三元组包含以下三部分的内容SDO_STARTING_OFFSET表明每个几何元素的第一个坐标在SDO_ORDINATES数组中的存储位置。
3、…Mt：N2）的表示称为三元组...…Mt称为标号，N1、N2为结点R为关系。当n≠0时，称Li为对结点N1的修饰。t≠0时，称Mj为对结点N2的修饰。
参考资料：网络：十字链表
网络：三元组
⑦ 对稀疏矩阵进行压缩存储的目的是什么
对稀疏矩阵进行压缩存储目的是节省存储空间。
存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算。
但对于稀疏矩阵而言，若用二维数组来表示，会重复存储了很多个0了，浪费空间，而且要花费时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。
(7)稀疏矩阵存储单元扩展阅读
优点
稀疏矩阵的计算速度更快，因为MATLAB只对非零元素进行操作，这是稀疏矩阵的一个突出的优点。假设矩阵A,B中的矩阵一样，计算2*A需要一百万次的浮点运算，而计算2*B只需要2000次浮点运算。
因为MATLAB不能自动创建稀疏矩阵，所以要用特殊的命令来得到稀疏矩阵。算术和逻辑运算都适用于稀疏矩阵。对于一个用二维数组存储的稀疏矩阵Amn，如果假设存储每个数组元素需要L个字节，那么存储整个矩阵需要m*n*L个字节。