Matrix CSR - Matrix Multiplication

Question

I have two square matrices A and B

I have to convert B to CSR Format and define the product of C

 A * B_csr = C 

I found a lot of information on the Internet regarding CSR Matrix - Vector Multiplication . Algorithm:

 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 need Matrix - Matrix multiplication.

Also, it seems that most algorithms use A_csr - vector multiplication where I need A * B_csr . My solution is to transfer two matrices before conversion, and then transfer the final product.

Can someone explain how to calculate the Matrix - CSR Matrix and / or CSR Matrix - Matrix product?

Answer 1

Here is a simple Python solution for Dense Matrix X CSR Matrix . It should be clear.

 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() 

Is CSR Matrix X Dense Matrix really just a CSR Matrix X Vector product sequence for each row of a dense matrix on the right? Therefore, for this it is enough to simply extend the code shown above to do this.

Moving forward, I suggest you not to code these routines yourself. If you use C ++ (tag based), you can look at Boost ublas , or Eigen . At first, the APIs may seem a little cryptic, but it really stands in the long run. First, you get access to much more functionality that you are likely to require in the future. Secondly, these implementations will be better optimized.