[SciPy-dev] sparsetools - new and (hopefully) improved!

[Travis Oliphant]

Nathan Bell wrote:

>I've rewritten sparse/sparsetools to speed up some of the slower bits
>in current code.  The previous implementation of CSR/CSC matrix
>addition, multiplication, and conversions were all very slow, often
>orders of magnitude slower than MATLAB or PySparse.
>
>  
>
Very nice.  Thank your for your help on these algorithms. 

>In the new implementation:
>- CSR<->CSC conversion is cheap (linear time)
>- sparse addition is fast (linear time)
>- sparse multiplication is fast (noticeably faster than MATLAB in my testing)
>- CSR column indices do not need to be sorted (same for CSC row indices)
>- the results of all the above operations contain no explicit zeros
>- COO->CSR and COO->CSC is linear time and sums duplicate entries
>
>
>This last point is useful for constructing stiffness/mass matrices.
>Matrix multiplication is essentially optimal (modulo Strassen-like
>algorithms) and is based on the SMMP algorithm I mentioned a while
>ago.
>  
>
Excellent.  Thank you.

>I implemented the functions in C++ with SWIG bindings. 
>
This isn't my most favorite way to include things in SciPy,  but it can 
work.  SciPy is all about whoever contributes and *their* favorite way.

>The code is available here:
>http://graphics.cs.uiuc.edu/~wnbell/sparse/sparse.tgz
>
>The sparse directory in the archive is indented to replace the sparse
>directory in scipy/Lib/
>I've successfully installed the above code with the standard scipy
>setup.py and all the unittests pass.
>  
>
This sounds good.

>A simple benchmark for sparse matrix multiplication SciPy and MATLAB
>is available here:
>http://graphics.cs.uiuc.edu/~wnbell/sparse/sparse_times.m
>http://graphics.cs.uiuc.edu/~wnbell/sparse/sparse_times.py
>
>On my laptop SciPy takes about 0.33 seconds to MATLAB's 0.55, so 40% faster.
>
>The code was all written my myself, aside from the bits pilfered from
>the NumPy SWIG examples and SciPy UMFPACK SWIG wrapper, so there
>shouldn't be any license issues.
>
>I welcome any comments, questions, and criticism you have.  If you
>know a better or more robust way to interface the C++ with Scipy
>please speak up!.
>  
>
The only other way I know of is weave, hand-written wrappers, 
boost-python (which seems like a totally different paradigm), and 
c-wrappers which are then called using c-types.

We might think about using weave, but swig is also fine because you 
don't have to have swig to get it to work.

How are you coming on getting access to the SVN repository?  I might 
also be able to give you access.  I looked over the code and could not 
find where the multiplication was actually being done (I got lost in the 
interface).  Does the tar file really contain all of your code?

Sparse matrices do need work and this has the potential to really help 
things.

-Travis




>
>Also, who should I contact regarding SVN commit privileges?
>
>  
>