[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 7.2.0.294 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