[SciPy-dev] sparsetools - new and (hopefully) improved!
cimrman3 at ntc.zcu.cz
Thu Jan 4 05:55:02 CST 2007
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
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()?
More information about the Scipy-dev