Sparse Matrix

• Sparse Matrix - Wikipedia

  https://en.wikipedia.org/wiki/Sparse_matrix

• Sparse Matrix 压缩格式

  • Coordinate (COO)

    COO很简单，就是使用3个数组，分别存储全部非零元的行下标（row index）、列下标（column index）和值（value）。每个元素需要用一个三元组来表示，分别是（行号、列号、数值），对应右边同色的一列。这种方式简单，但是记录的信息多，每个三元组自己可以定位，因此空间不是最优。 $$ {\rm Matrix}=\begin{bmatrix} 1 & 7 & 0 & 0 \ 0 & 2 & 8 & 0 \ 5 & 0 & 3 & 9 \ 0 & 6 & 0 & 4 \end{bmatrix} \ \begin{array} \ [0 & 0 & 1 & 1 & 2 & 2 & 2 & 3 & 3]&=& \text{row indices} \ [0 & 1 & 1 & 2 & 0 & 2 & 3 & 1 & 3]&=& \text{colum indices} \ [1 & 7 & 2 & 8 & 5 & 3 & 9 & 6 & 4]&=& \text{values} \end{array} $$

  • Compressed Sparse Row (CSR)

    CSR稍复杂，但是经常使用，在一些标准线性代数库或者数值运算库中能够看到此方式存储。CSR也需要三类数据来表达：行偏移、列号和数值。CSR不是三元组，而是整体的编码方式。对行下标进行了压缩，假设矩阵行数是m，则压缩后的数组长度为m+1，记作（row ptr），其中第i个元素（0-base）表示矩阵前i行的非零元个数 $$ {\rm Matrix}=\begin{bmatrix} 1 & 7 & 0 & 0 \ 0 & 2 & 8 & 0 \ 5 & 0 & 3 & 9 \ 0 & 6 & 0 & 4 \end{bmatrix} \ \begin{array} \ [0 & 2 & 4 & 7 & 9] & & & & &=& \text{row offsets} \ [0 & 1 & 1 & 2 & 0 & 2 & 3 & 1 & 3]&=& \text{colum indices} \ [1 & 7 & 2 & 8 & 5 & 3 & 9 & 6 & 4]&=& \text{values} \end{array} $$

  • Compressed Sparse Col (CSC)

    CSC是和CSR相对应的一种方式，即按列压缩的意思。以上图中矩阵为例：

    Column Offsets：	[0 2 5 7 9]
    Row Indices：	[0 2 0 1 3 1 2 2 3]
    Values：	[1 5 7 2 6 8 3 9 4]

  • 其他压缩方法以及效率对比分析

    https://blog.csdn.net/gggg_ggg/article/details/47402459

• Sparse Matrix 求解方法

  • direct methods (高斯消去、LU分解、QR分解)
  • iterative methods

• 123