[SciPy-Dev] Reordering methods for Sparse matrices

[Paul Nation]

I have yet to do a pull request for the RCM routine due to a lack of time (new baby, lectures, and conference organization).  However, the code itself is already written

https://github.com/qutip/qutip/blob/master/qutip/cy/graph_utils.pyx

and just needs to be reworked to match the SciPy format.  Since you reminded me, perhaps I can find time this weekend to push this out so at least the pull request is done.

Regards,

Paul

On Jun 21, 2014, at 9:54 AM, simon tournier <Simon.Tournier at alumni.enseeiht.fr> wrote:

> Hi,
> 
>>> I have written two sparse matrix reordering functions in Cython and 
>>> I
>>> am wondering if they would be worthy additions to the scipy.sparse 
>>> module?
>>> These are currently being used in our QuTiP library (qutip.org).
>>> 
>>> The first function finds the Reverse Cuthill-Mckee (RCM) ordering 
>>> [1]
>>> of a symmetric sparse matrix, similar to the Matlab ‘symrcm' 
>>> function.
>>> This is useful for reducing the bandwidth of the underlying matrix 
>>> to
>>> help eliminate fill-in when using direct or iterative solvers.
>>> If the matrix is not symmetric, it looks at A+trans(A).  Since the
>>> matrix is symmetric, this works for both CSR and CSC matrices.
>>> 
>>> The second, is a maximal traversal algorithm based on a 
>>> breadth-first-search
>>> method [2].  This returns a set of row permutations that makes
>>> the diagonal zero-free.  Since the permutation is not symmetric,
>>> this works only on CSC matrices.  Like RCM this is useful
>>> for preordering in both direct and iterative solvers.
> 
>> Sparse matrix permutation algorithms would certainly be a welcome 
>> addition.
>> 
>> As the code is already written, integrating it in scipy.sparse is
>> probably fairly simple. If you have questions,
> 
> Are these functions merged and now included in scipy.sparse or 
> scipy.sparse.csgraph ?
> If yes, I have not seen the documentation and I have missed some 
> points... so I'm sorry for the question.
> If no, is it planned ?
> 
> Theses orderings would be a nice feature for the sparse linear algebra, 
> in particular for both direct and iterative solvers.
> And a common version of RCM should be useful as explained in this 
> thread:
> http://mail.scipy.org/pipermail/scipy-dev/2011-December/016786.html
> 
> Moreover, to the question: "how to draw a good line between what 
> belongs in scipy.sparse and what doesn't" [jakevdp] asked here:
> https://github.com/scipy/scipy/pull/119
> and answered [rgommers] in the same thread by:
>     -- should have potential uses on more than one project that depends 
> on scipy
>     -- should appear in an introductory algorithm book such as 
> "Introduction to Algorithms", Cormen et al.
> from my experience of playing with sparse linear solvers, the useful 
> algorithms are: Random, column, minimum degree, Dulmage-Mendelsohn and 
> reverse Cuthill-McKee permutations. In other words, those included in 
> matlab 
> (http://www.mathworks.com/help/matlab/reordering-algorithms.html).
> 
> I have maybe wrong and I am just not able to find them in scipy (or 
> numpy).
> If not, is it planned to integrate them in scipy (or numpy) ?
> Are they already implemented in scikit-learn or sfepy or qutip or ... ?
> 
> 
> cheers,
> simon
> 
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev