CSR Matrix - Matrix multiplication

Question

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?

In the first loop what is i? Also, what is result, how is it initiated, what type does it contain? What are val and col? What is RowPtr? What is d? — bjpelcdev
– bjpelcdev, Commented Apr 13, 2015 at 7:56
@bjpelcdev i would be the ith index of C. The other values refer to the vectors associated with the CSR format. Anyways, I just provided the algorithm for reference, though I am interested in a different case. — Brian
– Brian, Commented Apr 13, 2015 at 17:25

paul-g · Accepted Answer · 2015-04-22 15:46:47Z

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.

Collectives™ on Stack Overflow

CSR Matrix - Matrix multiplication

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related