RCM
Reverse Cuthill McKee Ordering
RCM
is a FORTRAN90 library 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
3node or 6node 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:
576
  /
482
  
913
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:
789
  /
356
  
124
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.)
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Languages:
RCM is available in
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
MESH_BANDWIDTH,
a FORTRAN90 program which
returns the geometric bandwidth associated with a mesh of
elements of any order and in a space of arbitrary dimension.
SPARSE_CC,
a data directory which
contains a description and examples of the CC format,
("compressed column") for storing a sparse matrix,
including a way to write the matrix as a set of three files.
SPARSE_CR,
a data directory which
contains a description and examples of the CR format,
("compressed row") for storing a sparse matrix,
including a way to write the matrix as a set of three files.
SPARSEPAK,
a FORTRAN90 library which
solves sparse linear systems using the Reverse CuthillMcKee
reordering scheme.
TET_MESH_RCM,
a FORTRAN90 program 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 directory which
contains a description and
examples of order 3 triangulations.
TRIANGULATION ORDER6,
a directory which
contains a description and
examples of order 6 triangulations.
TRIANGULATION_RCM,
a FORTRAN90 program 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.
Reference:

HL Crane, Norman Gibbs, William Poole, Paul Stockmeyer,
Algorithm 508:
Matrix Bandwidth and Profile Reduction,
ACM Transactions on Mathematical Software,
Volume 2, Number 4, December 1976, pages 375377.

Alan George, Joseph Liu,
Computer Solution of Large Sparse Positive Definite Matrices,
Prentice Hall, 1981,
ISBN: 0131652745,
LC: QA188.G46

Norman Gibbs,
Algorithm 509:
A Hybrid Profile Reduction Algorithm,
ACM Transactions on Mathematical Software,
Volume 2, Number 4, December 1976, pages 378387.

Norman Gibbs, William Poole, Paul Stockmeyer,
An Algorithm for Reducing the Bandwidth
and Profile of a Sparse Matrix,
SIAM Journal on Numerical Analysis,
Volume 13, Number 2, April 1976, pages 236250.

John Lewis,
Algorithm 582:
The GibbsPooleStockmeyer and GibbsKing Algorithms
for Reordering Sparse Matrices,
ACM Transactions on Mathematical Software,
Volume 8, Number 2, June 1982, pages 190194.
Source Code:
Examples and Tests:
List of Routines:

ADJ_BANDWIDTH computes the bandwidth of an adjacency matrix.

ADJ_CONTAINS_IJ determines if (I,J) is in an adjacency structure.

ADJ_INSERT_IJ inserts (I,J) into an adjacency structure.

ADJ_PERM_BANDWIDTH computes the bandwidth of a permuted adjacency matrix.

ADJ_PERM_SHOW displays a symbolic picture of a permuted adjacency matrix.

ADJ_PRINT prints adjacency information.

ADJ_PRINT_SOME prints some adjacency information.

ADJ_SET sets up the adjacency information.

ADJ_SHOW displays a symbolic picture of an adjacency matrix.

DEGREE computes the degrees of the nodes in the connected component.

GENRCM finds the reverse CuthillMckee ordering for a general graph.

GRAPH_01_ADJ returns the adjacency vector for graph 1.

GRAPH_01_ADJ_NUM returns the number of adjacencies for graph 1.

GRAPH_01_LABEL returns the labels for graph 1.

I4_SWAP swaps two I4's.

I4_UNIFORM returns a scaled pseudorandom I4.

I4MAT_PRINT_SOME prints some of an I4MAT.

I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.

I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.

I4ROW_COMPARE compares two rows of an I4ROW.

I4ROW_SORT_A ascending sorts an I4ROW.

I4ROW_SWAP swaps two rows of an I4ROW.

I4VEC_HEAP_D reorders an I4VEC into an descending heap.

I4VEC_INDICATOR sets an I4VEC to the vector A(I)=I.

I4VEC_PRINT prints an I4VEC.

I4VEC_REVERSE reverses the elements of an I4VEC.

I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.

LEVEL_SET generates the connected level structure rooted at a given node.

LEVEL_SET_PRINT prints level set information.

PERM_CHECK checks that a vector represents a permutation.

PERM_INVERSE produces the inverse of a given permutation.

PERM_UNIFORM selects a random permutation of N objects.

R82VEC_PERMUTE permutes an R82VEC in place.

R8MAT_PRINT_SOME prints some of an R8MAT.

R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.

RCM renumbers a connected component by the reverse Cuthill McKee algorithm.

ROOT_FIND finds a pseudoperipheral node.

SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.

TIMESTAMP prints the current YMDHMS date as a time stamp.

TRIANGULATION_ORDER3_ADJ_COUNT counts adjacencies in a triangulation.

TRIANGULATION_ORDER3_ADJ_SET sets adjacencies in a triangulation.

TRIANGULATION_ORDER3_EXAMPLE2 returns an example triangulation.

TRIANGULATION_ORDER3_EXAMPLE2_SIZE returns the size of an example.

TRIANGULATION_ORDER3_NEIGHBOR_TRIANGLES determines triangle neighbors.

TRIANGULATION_ORDER6_ADJ_COUNT counts adjacencies in a triangulation.

TRIANGULATION_ORDER6_ADJ_SET sets adjacencies in a triangulation.

TRIANGULATION_ORDER6_EXAMPLE2 returns an example triangulation.

TRIANGULATION_ORDER6_EXAMPLE2_SIZE returns the size of an example.

TRIANGULATION_ORDER6_NEIGHBOR_TRIANGLES determines triangle neighbors.
You can go up one level to
the FORTRAN90 source codes.
Last revised on 03 January 2007.