Implementing Cuthill-McKee


#1

I am trying to implement Cuthill McKee on a number of large, sparse matrices. In particular, I would like to get the mapping from original row order to post-CM (or post-reverseCM) row order.

The only package that I can find that implements Cuthill McKee does this using nodes. In particular, the example linked above wants a Dict for the sparsity pattern (and another dict representing the node-types).

First, is there a cleaner way that anyone knows to do this? And, if not, is there a clean way to output the sparsity pattern as a dict?

As of now, I suspect I will just be writing a lot of for-loops, but I am hoping that there is a more elegant solution. Thank you!


#2

@dlfivefifty have you done this in ApproxFun yet?


#3

I implemented it a few years ago. Functio rcm at https://github.com/pjabardo/Makhno.jl/blob/master/src/numbering.jl

I remember it worked. I don’t know if it is efficient. Of course it was taylored for a specific data structure. I will try to convert it to use CSC sparse matrix this week end.


#4

No I haven’t. Would be nice to have in BandedMatrices.jl


#5

Thanks everyone. I found an acceptable intermediate solution for my particular problem that avoids the need for CM/RCM.

@Paulo_Jabardo, if you do ever convert your code to work with CSC Sparse Matrices, please do let me know.

@dlfivefifty, if I end up writing my own reasonably efficient code for RCM, I’ll try to contribute it to BandedMatrices.jl.