[SciPy-dev] sparse matrix multiplication - poor performance

Nathan Bell wnbell at gmail.com
Thu Dec 7 16:33:04 CST 2006

On 12/7/06, Nathan Bell <wnbell at gmail.com> wrote:
On 12/7/06, Joachim Dahl <dahl.joachim at gmail.com> wrote:
>  yes, this happens consistently for me with Matlab on a Linux P4
> computer.

I suggest you ask for your money back then :)  That should always be
an O(N) operation, no matter how convoluted the sparse storage format.

Anyway I've done some digging and I think the following are true:
  SPARSKIT is not actually used, although it is mentioned
  sparsetools is what actually computes the matrix matrix products
  sparsetools does an O(N^2) (in time) operation for sparse matrix multiplies[1]

I don't know Fortran so I can't say the last for certain.  My timing
results certainly suggest sub-optimal complexity.

Can anyone confirm this?  Should we look to alternatives such as
SPARSKIT [2] or SMMP and the like[3]? SPARSKIT seems to provide a
number of important utility routines that are also currently slow
(e.g. sparse matrix format conversions).

[1] http://projects.scipy.org/scipy/scipy/browser/trunk/Lib/sparse/sparsetools/spblas.f.src
[2] http://www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html
[3] http://www.mgnet.org/~douglas/ccd-codes.html

Nathan Bell wnbell at gmail.com

More information about the Scipy-dev mailing list