CSR矩阵 - 矩阵乘法 [英] CSR Matrix - Matrix multiplication

问题描述

我有两个方形矩阵 A 和 B

我必须将 B 转换为 CSR格式，并确定产品 C

  A * B_csr = C 
   
 
我在网上找到很多有关 CSR矩阵 - 向量乘法。算法是：
  for（k = 0; k  result [i] = 0; 
 
 for（i = 0; i  {
 for（k = RowPtr [i]; k  {
 result [i] = result [i] + Val [k] * d [Col [k] 
} 
} 
  
但是，我需要 Matrix -  Matrix 乘法。
 
 
 
此外，似乎大多数算法适用 A_csr  -  vector 乘法，其中我需要 A * B_csr 。我的解决方案是转换两个矩阵，然后转换，然后转置最终产品。
 
 
 
有人可以解释如何计算 Matrix  -  CSR Matrix 产品和/或 CSR Matrix  -  Matrix 产品？
解决方案
这里是一个简单的Python解决方案，用于 Dense Matrix X CSR Matrix 。它应该是不言自明的。 
  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]，
] b 
 res = [
 [0,0,0,0]，
 [0,0,0,0]，
 [0,0,0,0] 
 [0,0,0,0]，
] 
 
＃矩阵顺序，假设两个矩阵都是平方的
n = len（dense_matrix）
 $范围（n）中的i的
开始，结束= row_ptr [i]，row_ptr [i]，b_br + 1] 
 for范围（开始，结束）：
 col，csr_value = col_idx [j]，csr_values [j] 
用于范围dense_value = dense_matrix [k] [csr_row] 
 res [k] [col] + = csr_value * dense_value 
 csr_row + = 1 
 
 print res 
 $ b b 
 if __name__ =='__main__'：
 main（）
  
 code> CSR Matrix X Dense Matrix 实际上只是一系列 CSR Matrix X Vector 产品的每一行密集矩阵？因此，应该很容易扩展上面显示的代码来做到这一点。
 
 
 
前进，我建议你不要自己编写这些例程。如果您使用C ++（基于标记），那么您可以查看 Boost ublas ，或 Eigen 。 API可能看起来有点神秘，但它是非常值得的长期。首先，您可以访问更多的功能，这可能需要在将来。第二，这些实现将被更好地优化。
 
I have two square matrices A and B

I must convert B to CSR Format and determine the product C
A * B_csr = C
I have found a lot of information online regarding CSR Matrix - Vector multiplication. The algorithm is:
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]];
  }  
}
However, I require Matrix - Matrix multiplication.

Further, it seems that most algorithms apply A_csr - vector multiplication where I require A * B_csr. My solution is to transpose the two matrices before converting then transpose the final product.

Can someone explain how to compute a Matrix - CSR Matrix product and/or a CSR Matrix - Matrix product?
解决方案
Here is a simple solution in Python for the Dense Matrix X CSR Matrix. It should be self-explanatory. 
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 is really just a sequence of CSR Matrix X Vector product for each row of the dense matrix right? So it should be really easy to extend the code you show above to do this.

Moving forward, I suggest you don't code these routines yourself. If you are using C++ (based on the tag), then you could have a look at Boost ublas for example, or Eigen. The APIs may seem a bit cryptic at first but it's really worth it in the long term. First, you gain access to a lot more functionality, which you will probably require in the future. Second these implementations will be better optimised.

                        
这篇关于CSR矩阵 - 矩阵乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！