CODEWITHSUNDEEP
algorithmmatrixcomplexity-theorysparse-matrixeigen
Oran
Oran

Reputation: 41

Sparse matrix multiplication complexity

I want to express the computational complexity fo two algorithms: the sparse-matrix sparse-vector multiplication and the sparse-matrix sparse-matrix multiplication, as implemented in Eigen or Cusparse, using CSR representation.

I know that it depends on several parameters, especially the number of non-zero values in each elements.

However, I'm not able to find to find publications which details the complexity of such algorithms and expresses it using the O( ) notation.

Upvotes: 4

Views: 11977

Answers (1)

ggael
ggael

Reputation: 29205

Say you are multiplying A*B with A a m*k matrix with a non-zeros per column, and B a k*n matrix with b non-zeros per column. Then, the number of operations (* and +) is:

2*n*b*a

because for each of the n columns of B we have to loop through the b columns of A for which the corresponding elements of B are non-zeros, and then multiply-accumulate the respective a non-zeros. If properly implemented, as in Eigen or Cusparse, we have three nested loops with exactly n, b, and a iterations, the complexity is thus O(a*b*n).

Upvotes: 8

Related Questions