[SciPy-dev] sparse matrix multiplication - poor performance
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 126.96.36.1994 on a Linux P4
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
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  or SMMP and the like? SPARSKIT seems to provide a
number of important utility routines that are also currently slow
(e.g. sparse matrix format conversions).
Nathan Bell wnbell at gmail.com
More information about the Scipy-dev