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