Sparse matrix multiplication complexity

[WenlongGong]

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.

[stevengj]

@WenlongGong

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?

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

[tkelman]

I don’t think we call into suitesparse for spmm though, IIRC there’s a pure Julia implementation of the Gustavson algorithm. http://dl.acm.org/citation.cfm?id=355796