稀疏矩阵表示|集3（CSR）-yiteyi-C++库

如果矩阵中的大多数元素为零，则该矩阵称为稀疏矩阵。将零元素存储在矩阵中是浪费的，因为它们不会影响我们的计算结果。这就是为什么我们用比标准2D数组更高效的表示法来实现这些矩阵。使用更高效的表示，我们可以显著降低操作的空间和时间复杂性。我们在以下文章中讨论了4种不同的表述：

null

在本文中，我们将讨论稀疏矩阵的另一种表示形式，通常称为Yale格式。这个 CSR（压缩稀疏行）或耶鲁格式类似于稀疏矩阵的数组表示（在集合1中讨论）。我们用三个称为a，IA，JA的一维数组或向量来表示矩阵M（M*n）。允许 NNZ 表示M中非零元素的数量，并注意使用基于0的索引。

向量的大小为NNZ，它存储矩阵中非零元素的值。这些值按逐行遍历矩阵的顺序显示
IA向量的大小为m+1，它存储到（不包括）第i行的非零元素的累积数量。它由递归关系定义：
- IA[0]=0
- IA[i]=IA[i-1]+矩阵第（i-1）行中非零元素的数量
JA向量存储A向量中每个元素的列索引。因此，它的大小也是NNZ。

为了找到第一行中非零元素的数量，我们执行IA[i+1]–IA[i]。请注意，这种表示方式与基于数组的实现不同，后者的第二个向量存储非零元素的行索引。下面的例子展示了这些矩阵是如何表示的。例如：

Input : 0  0  0  0        5  8  0  0        0  0  3  0        0  6  0  0Solution: When the matrix is read row by           row, the A vector is [ 5 8 3 6]          The JA vector stores column indices          of elements in A hence, JA = [ 0 1 2            1]. IA[0] = 0. IA[1] = IA[0] + no            of non-zero elements in row 0           i.e 0 + 0 = 0.          Similarly,          IA[2] = IA[1] + 2 = 2          IA[3] = IA[2] + 1 = 3            IA[4] = IA[3]+1 = 4          Therefore IA = [0 0 2 3 4]          The trick is remember that IA[i]          stores NNZ upto and not-including           i row.Input : 10  20  0  0  0  0         0  30  0  4  0  0         0   0 50 60 70  0         0   0  0  0  0 80Output :  A = [10 20 30 4 50 60 70 80],         IA = [0 2 4 7 8]         JA = [0  1 1 3 2 3 4 5]

算法

SPARSIFY (MATRIX)Step 1: Set M to number of rows in MATRIXStep 2: Set N to number of columns in MATRIXStep 3: I = 0, NNZ = 0. Declare A, JA, and IA.         Set IA[0] to 0Step 4: for I = 0 ... N-1Step 5: for J = 0 ... N-1Step 5: If MATRIX [I][J] is not zero           Add MATRIX[I][J] to A           Add J to JA           NNZ = NNZ + 1        [End of IF]Step 6: [ End of J loop ]        Add NNZ to IA        [ End of I loop ]Step 7: Print vectors A, IA, JAStep 8: END

CPP

                         // CPP program to find sparse matrix rep-                       
                         // resentation using CSR                       
                         #include <algorithm>                       
                         #include <iostream>                       
                         #include <vector>                       
                         using                                     namespace                                     std;                       
           
                         typedef                                     std::vector<                                     int                                     > vi;                       
           
                         typedef                                     vector<vector<                                     int                                     > > matrix;                       
           
                         // Utility Function to print a Matrix                       
                         void                                     printMatrix(                                     const                                     matrix& M)                       
                         {                       
                                                 int                                     m = M.size();                       
                                                 int                                     n = M[0].size();                       
                                                 for                                     (                                     int                                     i = 0; i < m; i++) {                       
                                                 for                                     (                                     int                                     j = 0; j < n; j++)                       
                                                 cout << M[i][j] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                                                 }                       
                         }                       
           
                         // Utility Function to print A, IA, JA vectors                       
                         // with some decoration.                       
                         void                                     printVector(                                     const                                     vi& V,                                     char                                     * msg)                       
                         {                       
           
                                                 cout << msg <<                                     "[ "                                     ;                       
                                                 for_each(V.begin(), V.end(), [](                                     int                                     a) {                       
                                                 cout << a <<                                     " "                                     ;                       
                                                 });                       
                                                 cout <<                                     "]"                                     << endl;                       
                         }                       
           
                         // Generate the three vectors A, IA, JA                       
                         void                                     sparesify(                                     const                                     matrix& M)                       
                         {                       
                                                 int                                     m = M.size();                       
                                                 int                                     n = M[0].size(), i, j;                       
                                                 vi A;                       
                                                 vi IA = { 0 };                                     // IA matrix has N+1 rows                       
                                                 vi JA;                       
                                                 int                                     NNZ = 0;                       
           
                                                 for                                     (i = 0; i < m; i++) {                       
                                                 for                                     (j = 0; j < n; j++) {                       
                                                 if                                     (M[i][j] != 0) {                       
                                                 A.push_back(M[i][j]);                       
                                                 JA.push_back(j);                       
           
                                                 // Count Number of Non Zero                       
                                                 // Elements in row i                       
                                                 NNZ++;                       
                                                 }                       
                                                 }                       
                                                 IA.push_back(NNZ);                       
                                                 }                       
           
                                                 printMatrix(M);                       
                                                 printVector(A, (                                     char                                     *)                                     "A = "                                     );                       
                                                 printVector(IA, (                                     char                                     *)                                     "IA = "                                     );                       
                                                 printVector(JA, (                                     char                                     *)                                     "JA = "                                     );                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 matrix M = {                       
                                                 { 0, 0, 0, 0, 1 },                       
                                                 { 5, 8, 0, 0, 0 },                       
                                                 { 0, 0, 3, 0, 0 },                       
                                                 { 0, 6, 0, 0, 1 },                       
                                                 };                       
           
                                                 sparesify(M);                       
           
                                                 return                                     0;                       
                         }                       

输出：

0 0 0 0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 A = [ 1 5 8 3 6 1 ]IA = [ 0 1 3 4 6 ]JA = [ 4 0 1 2 1 4 ]

笔记

矩阵的稀疏性=（元素总数-非零元素数）/（元素总数）或（1–NNZ/mn）或（1–大小（A）/mn）。
基于直接数组的表示需要3*NNZ内存，而CSR需要（2*NNZ+m+1）内存。
只要 $space NNZ < (m*(n-1) - 1)/2$ .
与CSR类似，CSC代表压缩的稀疏列。它是CSR的柱状类似物。
“新”耶鲁格式进一步将A和JA向量压缩为1个向量。

工具书类 https://en.wikipedia.org/wiki/Sparse_matrix

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章