Overview
Cuthill-McKee treats the sparsity pattern of a matrix as a graph and applies a breadth-first style ordering from low-degree vertices to reduce bandwidth before matrix computations.
ExtendedSource checked
Cuthill-McKee Algorithm
Orders sparse matrix graph vertices to reduce matrix bandwidth.
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
- Cuthill-McKee ordering, CM ordering
Core Concepts
sparse matrixbandwidth reductiongraph orderingbreadth-first traversal
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 sparse matrix bandwidth affects storage or solver performance.
When Not to Use
- Avoid treating it as a solver; it is a reordering heuristic, not a direct numerical method.
What It Does
- Builds an ordering of graph vertices or sparse matrix rows.
- Tries to place connected vertices closer together in the ordering.
- Reduces matrix bandwidth for downstream numerical routines.
Use Cases
- Sparse linear systems
- Matrix reordering
- Preprocessing finite-element matrices
Inputs
- A sparse symmetric matrix or its graph representation.
Outputs
- A vertex or row-column ordering intended to reduce matrix bandwidth.
Pseudocode
- 1.Choose a low-degree start vertex.
- 2.Run degree-ordered breadth-first traversal.
- 3.Return the visited vertex order.
Canonical Example
- Input
- A sparse symmetric matrix or graph.
- Output
- A permutation of rows/columns or vertices.
- Explanation
- The permutation places nearby graph vertices close in the matrix ordering.
Implementation Notes
- The method is usually implemented with degree-aware breadth-first traversal.
Common Pitfalls
- Choosing poor starting vertices can reduce the quality of the ordering.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow vertices visited in degree-aware breadth-first order and the resulting sparse matrix permutation.
Step 1 of 3: Choose a low-degree start vertex.
graph-orderingNotes
Cuthill-McKee is a sparse matrix reordering heuristic; ordering quality depends on graph structure and starting vertex choice.
Sources (2)
What each reference supports for this entry.
Cuthill and McKee (1969)
PaperSupports the original sparse symmetric matrix bandwidth-reduction algorithm and its graph-ordering purpose.
Open sourceLiu and Sherman (1976)
PaperSupports the Cuthill-McKee sparse-matrix ordering context and comparison with the reverse ordering variant.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsReverse Cuthill-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 pageCuthill-McKee uses a breadth-first traversal order with degree-based tie-breaking to build a sparse-matrix ordering.
Often paired withCompressed Sparse Row
Cuthill-McKee orderings are often used before sparse matrix work stored or processed with compressed sparse formats.
Related Algorithms
Tags
GraphMatrixBreadth First Search