algorithm - IA 阵列的稀疏矩阵 CRS 逻辑

Question

我尝试实现稀疏矩阵存储格式。维基百科说:this

我需要CRS 算法。但是我无法理解算法到底。我有链接示例中的矩阵

0 0 0 0
5 8 0 0
0 0 3 0 
0 6 0 0

和3个数组

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

好的，我明白了，什么 A - 所有元素都不为零 JA - 行中第一个非零元素的列索引 但是 IA 的逻辑是什么？？？

Answer 1

AI[] vector 存储开始一行的位置。

例如 i 行的所有非零元素将它们的值存储在 A[k] 中及其相关的 j 指数在 AJ[k] 中其中 k是这样的

AI[i] <= k <= AI[i+1]-1

要掌握的中心思想包含在接下来的两行中:

AI[i] : 是在 row i 开头跳转的偏移量

AI[i+1]-1 : 是在 row i+1 开头跳转的偏移量, 但是 当我们删除 1 时，它成为 row i 的最后一个元素

---

为了说明这一点，我们可以在两种情况下计算矩阵向量乘积 y=A.x:密集格式和 CRS 格式(伪代码):

当 A 是稠密的时，我们有:

  for (i = 0; i < N; i++)       // row i
  {
      y[i] = 0;

      for (j = 0; j < N; j++)   // column j
          y[i] += A[i][j] * x[j];         
  }

与使用 CRS 格式存储 A 的情况进行比较:

   for (i = 0; i < N; i++)   // row i
   {  
      y[i]=0;

      for (k = AI[i]; k < AI[i+1]; k++) // nonzero element of row i
      {  
         y[i] += A[k] * x[AJ[k]];
      }  
   }