[SciPy-Dev] Reordering methods for Sparse matrices

[Paul Nation]

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.

[1] E. Cuthill and J. McKee, "Reducing the Bandwidth of Sparse Symmetric Matrices”, ACM '69 Proceedings of the 1969 24th national conference, (1969).

[2] I. S. Duff, K. Kaya, and B. Ucar, "Design, Implementation, and  Analysis of Maximum Transversal Algorithms", ACM Trans. Math. Softw. 38, no. 2, (2011).

Best regards,

Paul