rcm, a C++ code which computes the reverse Cuthill McKee ("RCM") ordering of the nodes of a graph.
The RCM ordering is frequently used when a matrix is to be generated whose rows and columns are numbered according to the numbering of the nodes. By an appropriate renumbering of the nodes, it is often possible to produce a matrix with a much smaller bandwidth.
The bandwidth of a matrix is computed as the maximum bandwidth of each row of the matrix. The bandwidth of a row of the matrix is essentially the number of matrix entries between the first and last nonzero entries in the row, with the proviso that the diagonal entry is always treated as though it were nonzero.
This library includes a few routines to handle the common case where the connectivity can be described in terms of a triangulation of the nodes, that is, a grouping of the nodes into sets of 3-node or 6-node triangles. The natural description of a triangulation is simply a listing of the nodes that make up each triangle. The library includes routines for determining the adjacency structure associated with a triangulation, and the test problems include examples of how the nodes in a triangulation can be relabeled with the RCM permutation.
Here is a simple example of how reordering can reduce the bandwidth. In our first picture, we have nine nodes:
5--7--6
| | /
4--8--2
| | |
9--1--3
The corresponding adjacency matrix is:
* . 1 . . . . 1 1
. * 1 . . 1 1 1 .
1 1 * . . . . . .
. . . * . . . 1 1
. . . . * . 1 1 .
. 1 . . . * 1 . .
. 1 . . 1 1 * . .
1 1 . 1 1 . . * .
1 . . 1 . . . . *
which has a disastrous bandwidth of 17 (lower and upper bandwidths
of 8, and 1 for the diagonal.)
If we keep the same connectivity graph, but relabel the nodes, we could get a picture like this:
7--8--9
| | /
3--5--6
| | |
1--2--4
whose adjacency matrix is:
* 1 1 . . . . . .
1 * . 1 1 . . . .
1 . * . 1 . . . .
. 1 . * . 1 . . .
. 1 1 . * 1 1 . .
. . . 1 1 * . 1 1
. . . . 1 . * 1 .
. . . . . 1 1 * 1
. . . . . 1 . 1 *
which has a bandwidth of 7 (lower and upper bandwidths
of 3, and 1 for the diagonal.)
The computer code and data files described and made available on this web page are distributed under the MIT license
rcm is available in a C++ version and a FORTRAN90 version and a MATLAB version.
MESH_BANDWIDTH, a C++ code which returns the geometric bandwidth associated with a mesh of elements of any order and in a space of arbitrary dimension.
QUAD_MESH_RCM, a C++ code which computes the reverse Cuthill-McKee (RCM) reordering for nodes in a mesh of 4-node quadrilaterals.
TET_MESH_RCM, a C++ code which reads files describing a tetrahedral mesh of nodes in 3D, and applies the RCM algorithm to produce a renumbering of the tet mesh with a reduced bandwidth.
TRIANGULATION ORDER3, a data directory which contains a description and examples of order 3 triangulations.
TRIANGULATION ORDER6, a data directory which contains a description and examples of order 6 triangulations.
TRIANGULATION_RCM, a C++ code which reads files describing a triangulation of nodes in 2D, and applies the RCM algorithm to produce a renumbering of the triangulation with a reduced bandwidth.