---
title: "MinimumBandwidthOrdering"
language: "en"
type: "Symbol"
summary: "As of Version 10, all the functionality of the GraphUtilities package is built into the Wolfram System. >>"
keywords: 
- matrix bandwidth matrix profile RCM reverse Cuthill McKee ordering Sloan algorithm
canonical_url: "https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html"
source: "Wolfram Language Documentation"
related_guides: 
  - 
    title: "Graphs & Networks"
    link: "https://reference.wolfram.com/language/guide/GraphsAndNetworks.en.md"
  - 
    title: "Graph Visualization"
    link: "https://reference.wolfram.com/language/guide/GraphVisualization.en.md"
  - 
    title: "Computation on Graphs"
    link: "https://reference.wolfram.com/language/guide/ComputationOnGraphs.en.md"
  - 
    title: "Graph Construction & Representation"
    link: "https://reference.wolfram.com/language/guide/GraphConstructionAndRepresentation.en.md"
  - 
    title: "Graphs and Matrices"
    link: "https://reference.wolfram.com/language/guide/GraphsAndMatrices.en.md"
  - 
    title: "Graph Properties & Measurements"
    link: "https://reference.wolfram.com/language/guide/GraphPropertiesAndMeasurements.en.md"
  - 
    title: "Graph Operations and Modifications"
    link: "https://reference.wolfram.com/language/guide/GraphModifications.en.md"
  - 
    title: "Statistical Analysis"
    link: "https://reference.wolfram.com/language/guide/RandomGraphs.en.md"
  - 
    title: "Social Network Analysis"
    link: "https://reference.wolfram.com/language/guide/SocialNetworks.en.md"
  - 
    title: "Graph Properties"
    link: "https://reference.wolfram.com/language/guide/GraphProperties.en.md"
  - 
    title: "Mathematical Data Formats"
    link: "https://reference.wolfram.com/language/guide/MathematicalDataFormats.en.md"
  - 
    title: "Discrete Mathematics"
    link: "https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md"
related_tutorials: 
  - 
    title: "Upgrading from Graph Utilities Package"
    link: "https://reference.wolfram.com/language/Compatibility/tutorial/GraphUtilities.en.md"
---
## GraphUtilities\`

# MinimumBandwidthOrdering

⚠ As of Version 10, all the functionality of the ``GraphUtilities`` package is built into the Wolfram System. [>>](https://reference.wolfram.com/language/Compatibility/tutorial/GraphUtilities.en.md)

MinimumBandwidthOrdering[g] attempts to find a vertex ordering that minimizes the bandwidth of the undirected graph g.

MinimumBandwidthOrdering[m] attempts to find row and column permutations that minimize the bandwidth of the matrix m.

## Details and Options

* To use ``MinimumBandwidthOrdering``, you first need to load the [Graph Utilities Package](https://reference.wolfram.com/language/GraphUtilities/guide/GraphUtilitiesPackage.en.md) using ``Needs["GraphUtilities`"]``.

* For a graph ``{V, E}`` with vertex ordering ``f``, the bandwidth of the graph is defined as
``Max{u, v}∈E  | f[u] - f[v] | ``.

* For a matrix ``m = (aij)``, the bandwidth is defined as ``Maxaij ≠ 0  | i - j | ``.

* For a symmetric matrix, the envelope size is defined as ``∑i Max(0, Maxaij ≠ 0i - j)``, which is the sum of the distance from the first element in each row to the diagonal position.

* ``MinimumBandwidthOrdering`` treats input graphs as undirected.

* The following options can be given:

|                  |           |                                 |
| ---------------- | --------- | ------------------------------- |
| Method           | Automatic | method to use                   |
| RefinementMethod | Automatic | method used to improve ordering |
| RecursionMethod  | None      | recursion method to use         |

---

## Examples (4)

### Basic Examples (2)

```wl
In[1]:= Needs["GraphUtilities`"]
```

This defines a small graph:

```wl
In[2]:= g = {b -> c, c -> d, c -> e, d -> f, e -> f, a -> b};
```

This numbers the vertices using ordering from ``VertexList`` :

```wl
In[3]:= order = Thread[VertexList[g] -> Range[6]]

Out[3]= {b -> 1, c -> 2, d -> 3, e -> 4, f -> 5, a -> 6}

In[4]:= GraphPlot[g /. order, VertexLabeling -> True]

Out[4]= [image]
```

This finds the bandwidth of the graph with the given ordering:

```wl
In[5]:= Max[Map[Abs[Subtract@@#]&, g /. order]]

Out[5]= 5
```

This finds a vertex ordering that attempts to minimize the bandwidth:

```wl
In[6]:= neworder = Thread[MinimumBandwidthOrdering[g] -> Range[6]]

Out[6]= {a -> 1, b -> 2, c -> 3, e -> 4, d -> 5, f -> 6}
```

This renumbers the vertices using the minimum bandwidth ordering:

```wl
In[7]:= GraphPlot[g /. neworder, VertexLabeling -> True]

Out[7]= [image]
```

This finds the bandwidth using the vertex ordering given by ``MinimumBandwidthOrdering`` :

```wl
In[8]:= Max[Map[Abs[Subtract@@#]&, g /. neworder]]

Out[8]= 2
```

---

```wl
In[1]:= Needs["GraphUtilities`"]
```

This defines a rectangular matrix:

```wl
In[2]:=
m = (|   |   |   |   |   |   |   |   |
| - | - | - | - | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 |
| 0 | 0 | 2 | 1 | 0 | 0 | 3 | 2 |
| 0 | 2 | 1 | 2 | 0 | 0 | 0 | 3 |
| 0 | 1 | 2 | 3 | 0 | 2 | 0 | 0 |
| 0 | 0 | 0 | 2 | 0 | 0 | 2 | 1 |
| 0 | 2 | 3 | 0 | 2 | 1 | 0 | 0 |);
```

This finds the row and column ordering that attempts to minimize the bandwidth of the matrix:

```wl
In[3]:= {r, c} = MinimumBandwidthOrdering[m]

Out[3]= {{6, 4, 3, 2, 5, 1}, {5, 6, 2, 3, 4, 8, 7, 1}}
```

Plots of the matrix before and after the ordering show a decrease in bandwidth:

```wl
In[4]:= {MatrixPlot[m], MatrixPlot[m[[r, c]]]}

Out[4]= {[image], [image]}
```

### Options (1)

#### Method (1)

This finds orderings of a matrix using the methods ``"RCMD"`` and ``"Sloan"`` :

```wl
In[1]:= Needs["GraphUtilities`"]

In[2]:=
m = (⁠|   |   |   |   |   |   |   |   |   |   |
| :- | :- | :- | :- | :- | :- | :- | :- | :- | :- |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 2 | 2 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 2 | 1 | 1 | 2 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 2 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 2 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |⁠);

In[3]:=
{r1, c1} = MinimumBandwidthOrdering[m, Method -> "RCMD"];
{r2, c2} = MinimumBandwidthOrdering[m, Method -> "Sloan"];
```

The maximum bandwidth given by ``"RCMD"`` is smaller; envelope size given by ``"Sloan"`` is smaller:

```wl
In[4]:= {MatrixPlot[m[[r1, c1]]], MatrixPlot[m[[r2, c2]]]}

Out[4]= {[image], [image]}
```

### Applications (1)

One of the applications of minimum bandwidth ordering is in optimizing cache performance of numerical calculations. For example, in multiplying a sparse matrix with a vector, if the matrix is preordered to minimize the bandwidth, then elements of the vector will not be accessed randomly, thus improving cache performance. Because ordering itself takes time, this improvement in cache performance would be beneficial only if the matrix-vector product operation is to be performed repeatedly many times.

This generates a banded matrix, and then randomly permutes it:

```wl
In[1]:= Needs["GraphUtilities`"]

In[2]:= n = 200000;a = SparseArray[{Band[{1, 1}] -> Random[], Band[{1, 2}] -> Random[], Band[{2, 1}] -> Random[]}, {n, n}];

In[3]:=
p = Ordering[RandomReal[1, {n}]];
q = Ordering[RandomReal[1, {n}]];
b = a[[p, q]];
```

This performs a matrix-vector product 50 times:

```wl
In[4]:=
x = RandomReal[1, {n}];
Table[bx = b.x;, {50}];//Timing

Out[4]= {5.29233, Null}
```

This permutes the matrix to minimize the bandwidth and permutes the vector correspondingly:

```wl
In[5]:=
{r, c} = MinimumBandwidthOrdering[b];
aa = b[[r, c]];
xx = x[[c]];
```

This shows that the matrix-vector product now takes less time:

```wl
In[6]:= Table[aax = aa.xx, {50}];//Timing

Out[6]= {1.06007, Null}
```

This checks that the answer is the same, subject to a permutation:

```wl
In[7]:= aax == bx[[r]]

Out[7]= True
```

## See Also

* [MinCut](https://reference.wolfram.com/language/GraphUtilities/ref/MinCut.en.md)

## Tech Notes

* [Upgrading from Graph Utilities Package](https://reference.wolfram.com/language/Compatibility/tutorial/GraphUtilities.en.md)
* [Graph Utilities Package](https://reference.wolfram.com/language/GraphUtilities/tutorial/GraphUtilities.en.md)

## Related Guides

* [Graph Utilities Package](https://reference.wolfram.com/language/GraphUtilities/guide/GraphUtilitiesPackage.en.md)
* [Graphs & Networks](https://reference.wolfram.com/language/guide/GraphsAndNetworks.en.md)
* [Graph Visualization](https://reference.wolfram.com/language/guide/GraphVisualization.en.md)
* [Computation on Graphs](https://reference.wolfram.com/language/guide/ComputationOnGraphs.en.md)
* [Graph Construction & Representation](https://reference.wolfram.com/language/guide/GraphConstructionAndRepresentation.en.md)
* [Graphs and Matrices](https://reference.wolfram.com/language/guide/GraphsAndMatrices.en.md)
* [Graph Properties & Measurements](https://reference.wolfram.com/language/guide/GraphPropertiesAndMeasurements.en.md)
* [Graph Operations and Modifications](https://reference.wolfram.com/language/guide/GraphModifications.en.md)
* [Statistical Analysis](https://reference.wolfram.com/language/guide/RandomGraphs.en.md)
* [Social Network Analysis](https://reference.wolfram.com/language/guide/SocialNetworks.en.md)
* [Graph Properties](https://reference.wolfram.com/language/guide/GraphProperties.en.md)
* [Mathematical Data Formats](https://reference.wolfram.com/language/guide/MathematicalDataFormats.en.md)
* [Discrete Mathematics](https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md)