Overview
Reverse Cuthill-McKee computes a Cuthill-McKee-style graph ordering and reverses it, a common heuristic for reducing the envelope or profile of sparse symmetric matrices.
ExtendedSource checked
Reverse Cuthill-McKee Algorithm
Reverses Cuthill-McKee ordering to improve sparse matrix bandwidth profiles.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Advanced
- Family
- Sparse matrix ordering
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Not ready
- Visualization
- Not ready
- Aliases
- RCM, Reverse Cuthill-McKee ordering
Core Concepts
sparse matrixbandwidth reductionprofile reductiongraph ordering
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(n + m)
When to Use
- Use when a reverse ordering improves sparse matrix profile or fill behavior.
When Not to Use
- Do not assume it is optimal; it remains a heuristic reordering method.
What It Does
- Computes a Cuthill-McKee-style vertex order.
- Reverses that order before applying it to a matrix.
- Targets sparse matrix bandwidth and profile reduction.
Use Cases
- Sparse direct solvers
- Finite-element matrix preprocessing
- Matrix reordering
Inputs
- A sparse symmetric matrix graph and a Cuthill-McKee-style ordering pass.
Outputs
- A reversed sparse matrix ordering for bandwidth or profile reduction.
Pseudocode
- 1.Compute a Cuthill-McKee order.
- 2.Reverse the order.
- 3.Return the reversed permutation.
Canonical Example
- Input
- A sparse symmetric matrix graph.
- Output
- A reversed bandwidth-reducing vertex order.
- Explanation
- The resulting permutation is applied to the matrix rows and columns.
Implementation Notes
- The main implementation difference is reversing the Cuthill-McKee result.
Common Pitfalls
- Confusing reverse Cuthill-McKee with a different traversal instead of a reversed ordering variant.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the Cuthill-McKee traversal order, then reverse it before applying the matrix permutation.
Step 1 of 3: Compute a Cuthill-McKee order.
graph-orderingNotes
Reverse Cuthill-McKee uses the same ordering idea as Cuthill-McKee but reverses the final order; this can improve sparse matrix profile or bandwidth behavior in many solver workflows.
Sources (2)
What each reference supports for this entry.
Liu and Sherman (1976)
PaperSupports reverse Cuthill-McKee ordering and its profile-reduction comparison with Cuthill-McKee.
Open sourceMathWorks symrcm documentation
DocumentationDocuments the reverse Cuthill-McKee ordering as a practical sparse-matrix preordering method.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Variant ofCuthill-McKee Algorithm
Numerical Methods · Extended
Reverse Cuthill-McKee is a variant of Cuthill-McKee that reverses the final ordering and can reduce sparse matrix bandwidth or profile in many workflows.
Compare with thisRelationships
View full relationship pageReverse Cuthill-McKee uses degree-ordered breadth-first traversal before reversing the resulting order.
Often paired withCompressed Sparse Row
Reverse Cuthill-McKee is often used before sparse matrix operations stored in compressed sparse formats.
Variant ofCuthill-McKee Algorithm
Reverse Cuthill-McKee is a variant of Cuthill-McKee that reverses the final ordering and can reduce sparse matrix bandwidth or profile in many workflows.
Related Algorithms
Tags
GraphMatrixBreadth First Search