[SciPy-dev] sparse matrix multiplication - poor performance

[Travis Oliphant]

Nathan Bell wrote:

>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).
>  
>

The licensing for SPARSKIT is (was) not suitable for use in SciPy.   I 
have used it in the past but couldn't because of licensing issues.

-Travis