稀疏矩阵的数据结构_稀疏矩阵 matlab_稀疏矩阵存储格式总结+存储效率对比:COO,CSR,DIA,ELL,HYB
本文关键词：稀疏矩阵，由笔耕文化传播整理发布。
稀疏矩阵是指矩阵中的元素大部分是0的矩阵，事实上，实际问题中大规模矩阵基本上都是稀疏矩阵，很多稀疏度在90%甚至99%以上。因此我们需要有高效的稀疏矩阵存储格式。本文总结几种典型的格式：COO,CSR,DIA,ELL,HYB。
（1）Coordinate（COO）
这是最简单的一种格式，每一个元素需要用一个三元组来表示，分别是（行号，列号，数值），对应上图右边的一列。这种方式简单，但是记录单信息多（行列），每个三元组自己可以定位，因此空间不是最优。
（2）Compressed Sparse Row (CSR)
CSR是比较标准的一种，也需要三类数据来表达：数值，列号，以及行偏移。CSR不是三元组，而是整体的编码方式。数值和列号与COO一致，表示一个元素以及其列号，行偏移表示某一行的第一个元素在values里面的起始偏移位置。如上图中，第一行元素1是0偏移，第二行元素2是2偏移，第三行元素5是4偏移，第4行元素6是7偏移。在行偏移的最后补上矩阵总的元素个数，本例中是9。
CSC是和CSR相对应的一种方式，即按列压缩的意思。
以上图中矩阵为例：
Values： [1 5 7 2 6 8 3 9 4]
Row Indices：[0 2 0 1 3 1 2 2 3]
Column Offsets：[0 2 5 7 9]
再来看一个CSR的例子[4]：
（3）ELLPACK (ELL)
用两个和原始矩阵相同行数的矩阵来存：第一个矩阵存的是列号，第二个矩阵存的是数值，行号就不存了，用自身所在的行来表示；这两个矩阵每一行都是从头开始放，如果没有元素了就用个标志比如*结束。 上图中间矩阵有误，第三行应该是 0 2 3。
注：这样如果某一行很多元素，那么后面两个矩阵就会很胖，其他行结尾*很多，浪费。可以存成数组，比如上面两个矩阵就是：
0 1 * 1 2 * 0 2 3 * 1 3 *
1 7 * 2 8 * 5 3 9 * 6 4 *
但是这样要取一行就比较不方便了
（4）Diagonal (DIA)
对角线存储法，按对角线方式存，列代表对角线，行代表行。省略全零的对角线。(从左下往右上开始：第一个对角线是零忽略，第二个对角线是5，6，第三个对角线是零忽略，，第四个对角线是1，2，3，4，第五个对角线是7，8，9，第六第七个对角线忽略)。[3]
这里行对应行，所以5和6是分别在第三行第四行的，前面补上无效元素*。如果对角线中间有0，存的时候也需要补0，所以如果原始矩阵就是一个对角性很好的矩阵那压缩率会非常高，比如下图，但是如果是随机的那效率会非常糟糕。
（5）Hybrid (HYB) ELL + COO
为了解决（3）ELL中提到的，如果某一行特别多，造成其他行的浪费，那么把这些多出来的元素（比如第三行的9，其他每一行最大都是2个元素）用COO单独存储。
选择稀疏矩阵存储格式的一些经验[2]：
一些特殊类型矩阵的存储效率（数值越小说明压缩率越高，即存储效率越高）:
Structured Mesh
Unstructured Mesh
Random matrix
Power-Law Graph
格式适用性总结：
下面摘自[2]
6. Skyline Storage Format
The skyline storage format is important for the direct sparse solvers, and it is well suited for Cholesky or LU decomposition when no pivoting is required.
The skyline storage format accepted in Intel MKL can store only triangular matrix or triangular part of a matrix. This format is specified by two arrays: values and pointers . The following table describes these arrays:
valuesA scalar array. For a lower triangular matrix it contains the set of elements from each row of the matrix starting from the first non-zero element to and including the diagonal element. For an upper triangular matrix it contains the set of elements from each column of the matrix starting with the first non-zero element down to and including the diagonal element. Encountered zero elements are included in the sets.
pointersAn integer array with dimension ( m +1) , where m is the number of rows for lower triangle (columns for the upper triangle). pointers ( i ) - pointers (1)+1 gives the index of element in values that is first non-zero element in row (column) i . The value of pointers ( m +1) is set to nnz + pointers (1) , where nnz is the number of elements in the array values .
7. Block Compressed Sparse Row Format (BSR)
The Intel MKL block compressed sparse row (BSR) format for sparse matrices is specified by four arrays: values , columns , pointerB , and pointerE . The following table describes these arrays.
valuesA real array that contains the elements of the non-zero blocks of a sparse matrix. The elements are stored block-by-block in row-major order. A non-zero block is the block that contains at least one non-zero element. All elements of non-zero blocks are stored, even if some of them is equal to zero. Within each non-zero block elements are stored in column-major order in the case of one-based indexing, and in row-major order in the case of the zero-based indexing.
columnsElement i of the integer array columns is the number of the column in the block matrix that contains the i -th non-zero block.
pointerBElement j of this integer array gives the index of the element in the columns array that is first non-zero block in a row j of the block matrix.
pointerEElement j of this integer array gives the index of the element in the columns array that contains the last non-zero block in a row j of the block matrix plus 1.
[1] Sparse Matrix Representations & Iterative Solvers, Lesson 1 by Nathan Bell.
[2]
[3]
[4]
[5] Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors, Nathan Bell and Michael Garland, Proceedings of Supercomputing '09
[6] Efficient Sparse Matrix-Vector Multiplication on CUDA, Nathan Bell and Michael Garland, NVIDIA Technical Report NVR-2008-004, December 2008
本文关键词：稀疏矩阵，由笔耕文化传播整理发布。
本文编号：77464
本文链接：https://www.wllwen.com/wenshubaike/jyzy/77464.html
