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 ex…

Perhaps it would be good to agree on a representation of adjacency and degree and then make a collection of bandwidth reduction algorithms in some central place? It could be called BandwidthReduction.jl or something similar? Then other packages, e.g. FinEtools.jl, LightGraphs.jl, BandedMatrices.jl c…

Hi, I just wanted to express interest in this area too. I had previously been using AMD and related algorithms, and recently started wondering about implementing an ordering algorithm too – until I found this thread that is. Not sure yet if CM/RCM will perform well in our case (robotics navigation…

Hello, Which Julia package would you recommend for the Cuthill-McKee algorithm? I couldn’t find it in LightGraphs.jl

Shameless plug: FinEtools.jl has it. Copy and paste, if you must. Or use with FinEtools.jl.

Thanks @PetrKryslUCSD , that’s a great resource! I’d recommend using LightGraphs.jl since there is capability to get the adjacency matrix but not yet to extract a variable ordering for fill-in / bandwidth-reduction / pivoting. We have a great interest in this problem as mentioned before although we…

The GPS paper acknowledged that the results of GPS of reducing the bandwidth were not that much of an improvement on RCM, and their main claim was that their algorithm ran so much faster. The curious thing is that I remember a friend telling me that he implemented both RCM and GPS and they ran in ap…

[image] dehann: AMD.jl, [external C dependency, license unclear] In what sense is the license unclear? https://github.com/JuliaSmoothOptimizers/AMD.jl/blob/master/LICENSE.md

Hi @PetrKryslUCSD , oh that’s interesting and would be great if RCM gets good performance since it’s already available as native Julia code and well connected to LightGraphs.jl. Just for reference, I did recently come across another claim that some adaptations of GPS is faster, although its not imme…

The library libamd.so that is used by AMD.jl is licensed differently, likely LGPL – following: https://opensuse.pkgs.org/tumbleweed/opensuse-oss-x86_64/libamd2-2.4.6-35.3.x86_64.rpm.html If the functionality is coming through SuiteSparse (e.g. CCOLAMD) then it’s unclear if that requires a commerc…

Implementing Cuthill-McKee

Specific Domains Numerics

PetrKryslUCSD August 6, 2020, 4:20pm 31

3 Likes

Topic		Replies	Views
ANN: Reverse Cuthill-McKee sparse matrix renumbering General Usage	3	788	October 10, 2020
What is the fastest way of realizing transpose of a CSR (or CSC) matrix? Performance sparse	33	424	March 19, 2026
Using GraphBLAS (from SuiteSparse) to speed up Julia sparse matrix operations Internals & Design sparse	0	1311	May 31, 2021
SymRCM doesn't seem to help linear solver to perform Performance question	12	1047	October 22, 2021
CSC kills the prospect of multithreading. Shouldn't Julia use CSR? Julia at Scale sparse	47	3438	March 20, 2024

Implementing Cuthill-McKee

Related topics