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

[Robert Cimrman]

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

Hi Nathan, I have not had time to look at your code yet (just returned 
from holidays) but the description looks great!

One umfpack-related note - the solver requires the CSC/CSR column/row 
indices sorted in ascending order. Does your implementation contain a 
function to ensure_sorted_indices()?

r.