CSR矩阵 - 矩阵乘法

Question

我有两个方阵 A 和 B

我必须将 B 转换为 CSR 格式 并确定乘积 C

A * B_csr = C

我在网上找到了很多关于CSR矩阵 - 向量乘法的信息。算法如下：

for (k = 0; k < N; k = k + 1)
  result[i] = 0;

for (i = 0; i < N; i = i + 1)
{  
  for (k = RowPtr[i]; k < RowPtr[i+1]; k = k + 1)
  {  
    result[i] = result[i] + Val[k]*d[Col[k]];
  }  
}

然而，我需要进行矩阵-矩阵乘法。

此外，大多数算法似乎适用于A_csr-向量乘法，而我需要A * B_csr。我的解决方案是在转换之前对两个矩阵进行转置，然后转置最终的乘积。

有人能解释一下如何计算矩阵-CSR矩阵乘积和/或CSR矩阵-矩阵乘积吗？

- Brian

---

在第一个循环中，i是什么？另外，result是什么，它是如何初始化的，它包含什么类型？val和col是什么？RowPtr是什么？d是什么？ - bjpelcdev

@bjpelcdev i 将是 C 的第 ith 个索引。其他值指的是与 CSR 格式相关联的向量。无论如何，我只是提供算法作为参考，尽管我对另一种情况很感兴趣。 - Brian

Answer 1

这里有一个Python的简单解决方案，用于 密集矩阵X CSR矩阵 的转换。它应该很容易理解。

def main():
  # 4 x 4 csr matrix
  #    [1, 0, 0, 0],
  #    [2, 0, 3, 0],
  #    [0, 0, 0, 0],
  #    [0, 4, 0, 0],
  csr_values = [1, 2, 3, 4]
  col_idx    = [0, 0, 2, 1]
  row_ptr    = [0, 1, 3, 3, 4]
  csr_matrix = [
      csr_values,
      col_idx,
      row_ptr
      ]

  dense_matrix = [
      [1, 3, 3, 4],
      [1, 2, 3, 4],
      [1, 4, 3, 4],
      [1, 2, 3, 5],
      ]

  res = [
      [0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0],
      ]

  # matrix order, assumes both matrices are square
  n = len(dense_matrix)

  # res = dense X csr
  csr_row = 0 # Current row in CSR matrix
  for i in range(n):
    start, end = row_ptr[i], row_ptr[i + 1]
    for j in range(start, end):
      col, csr_value = col_idx[j], csr_values[j]
      for k in range(n):
        dense_value = dense_matrix[k][csr_row]
        res[k][col] += csr_value * dense_value
    csr_row += 1

  print res


if __name__ == '__main__':
  main()

CSR Matrix X Dense Matrix实际上只是针对密集矩阵的每一行进行CSR Matrix X Vector乘积的序列。所以，扩展您上面展示的代码以执行此操作应该非常容易。

未来，我建议您不要自己编写这些例程。如果您正在使用C++（基于标签），则可以查看例如Boost ublas或Eigen。API可能一开始看起来有点神秘，但从长远来看它真的很值得。首先，您可以获得更多功能，这在将来可能会需要。其次，这些实现将更好地优化。

- paul-g