Sparse matrix multiplication complexity


I’m trying to confirm the spmatmul() function in julia, for sparse matrix multiplication, has the same complexity (using big O notation) with Matlab sparse matrix multiplication(by Dr. Tim Davis). For A*B, A is m by n, B is n by n, according to Davis’s book, it has O(m+n+flops+nnz(B)) complexity with his code. Does Julia’s spmatmul() has the same complexity?

All comments are welcome.


It should, especially since Julia uses Tim Davis’ SuiteSparse code.


I don’t think we call into suitesparse for spmm though, IIRC there’s a pure Julia implementation of the Gustavson algorithm.