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

Robert Cimrman cimrman3 at ntc.zcu.cz
Fri Jan 5 08:44:33 CST 2007

Nathan Bell wrote:
> 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.

ok, I agree that the flag is not a good idea.

> 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

Here by 'conversion' you mean CSR->CSC->CSR and ensure_sorted_indices() 
will be based on that? If yes, and assuming that a temporary copy is 
made (am I right?) what about ensure_sorted_indices() working inplace 
(just (quick,arg)sorting row by row)?

I would like both
mtx2 = mtx.ensure_sorted_indices()
mtx.ensure_sorted_indices( inplace = True ) (returning None?)

Well, I must try it first to be able to have relevant comments, but my 
computer is undergoing a software upgrade now and various stuff does not 
work. So sorry for the possibly unclear/stupid questions. :)

anyway thanks for your work on the sparse module!

More information about the Scipy-dev mailing list