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

Nathan Bell wnbell at gmail.com
Fri Jan 5 08:02:49 CST 2007

On 1/5/07, Robert Cimrman <cimrman3 at ntc.zcu.cz> wrote:
> Good! Going CSR->CSC->CSR would be too inefficient, IMHO. Maybe we could
> add a flag to the CSR/CSC matrix class saying that it has sorted indices
> to make the check trivial. It should be added as keyword argument to the
> matrix constructor, too.

Well, while that's certainly possible I'd recommend not doing it.
First, it's possible for the flag to become invalid if the user
manipulates the data directly.  This leads to hard to find and hard to
reproduce errors.  Second, the conversion is an extremely fast
linear-time operation.  In my testing, one conversion is only twice as
expensive as a copy()[1].  In the case of UMFPACK, a couple
conversions will be insignificant to the time required by the LU
factorization.  In short, I think it's fair to assume that any call to
ensure_sorted_indices() will be followed by some non-trivial algorithm
that dominates the overall cost.

I plan to commit my code to SVN later today.  Once you're up and
running with the new sparsetools the relative costs of the
conversions/operations will be more clear.

[1] for a 1Mx1M matrix with 5M nnz, the conversion takes 1.02 seconds, while
a copy alone takes 0.53 seconds
Nathan Bell wnbell at gmail.com

More information about the Scipy-dev mailing list