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
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@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@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev
participants (2)
-
Paul Nation -
simon tournier