CODEWITHSUNDEEP
cmatrixsparse-matrixmatrix-multiplication
user10561105
user10561105

Reputation:

Sparse matrix multplication in C

I have 2 sparse matrix files in matrix-market format:

row col val
1   1   3.0
1   2   1.0
2   3   2.0
etc...

Currently, I have split the files into 6 arrays: 

row_A[], col_A[], val_A[], row_B[] …

Which contain the row index, column index and value respectively.

I would like to multiply the two matrices easily without having to convert them to dense matrix format first. Is there an algorithm for doing this?

I found this pseudocode on Quora but I'm unsure if its the it's the best implementation, or how it would be implemented in C: https://www.quora.com/What-is-the-C-program-for-the-multiplication-of-two-sparse-matrices

multiply(A,B):
  for r in A.rows:
    for c in A.rows[r]:
      for k in B.rows[c]:
        C[r,k] += A[r,c]*B[c,k]

Thanks.

Upvotes: 2

Views: 2180

Answers (2)

Aznaveh
Aznaveh

Reputation: 578

There are sparse packages that do the multiplication for you. Have you tried Csparse inside SuiteSparse? http://faculty.cse.tamu.edu/davis/suitesparse.html

You don't even need to convert the matrix format. However there are ways to feed in triplet format too.

Upvotes: 1

SparseSolverCodes
SparseSolverCodes

Reputation: 71

It is not a good idea to multiply sparse matrices, because the resulting matrix will be dense anyway. You algorithm, apparently, consists of sequential multiplication of sparse matrices by a vector: a matrix is multiplied by a vector, then another matrix is multiplied by the obtained product, and so on. It would be wise to stick to that computational pattern, thus saving CPU time and the amount of RAM (the latter would be large if you intend to obtain and store the product of two sparse matrices).

Upvotes: 0

Related Questions