rcm
rcm,
an Octave 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.)
Licensing:
The information on this web page is distributed under the MIT license.
Languages:
rcm is available in
a C++ version and
a Fortran90 version and
a MATLAB version and
an Octave version.
Related Data and Programs:
rcm_test
mesh_bandwidth,
an Octave code which
returns the geometric bandwidth associated with a mesh of
elements of any order and in a space of arbitrary dimension.
quadrilateral_mesh_rcm,
an Octave code which
computes the Reverse Cuthill McKee (RCM) reordering for nodes
in a mesh of 4-node
quadrilaterals.
tet_mesh_rcm,
an Octave 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 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,
an Octave 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.
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 375-377.
-
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 378-387.
-
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 236-250.
-
John Lewis,
Algorithm 582:
The Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms
for Reordering Sparse Matrices,
ACM Transactions on Mathematical Software,
Volume 8, Number 2, June 1982, pages 190-194.
Source Code:
-
adj_bandwidth.m,
computes the bandwidth of an adjacency matrix.
-
adj_contains_ij.m,
determines if (I,J) is in an adjacency structure.
-
adj_insert_ij.m,
inserts (I,J) into an adjacency structure.
-
adj_perm_bandwidth.m,
computes the bandwidth of a permuted adjacency matrix.
-
adj_perm_show.m,
displays a symbolic picture of a permuted adjacency matrix.
-
adj_print.m,
prints adjacency information.
-
adj_print_some.m,
prints some adjacency information.
-
adj_set.m,
sets up the adjacency information.
-
adj_show.m,
displays a symbolic picture of an adjacency matrix.
-
degree.m,
computes the degrees of the nodes in the connected component.
-
genrcm.m,
finds the reverse Cuthill-Mckee ordering for a general graph.
-
graph_01_adj.m,
returns the adjacency vector for graph 1.
-
graph_01_adj_num.m,
returns the number of adjacencies for graph 1.
-
i4_sign.m,
returns the sign of an I4.
-
i4_swap.m,
swaps two integer values.
-
i4_uniform.m,
returns a scaled pseudorandom I4.
-
i4col_compare.m,
compares two columns of an I4COL.
-
i4col_sort_a.m,
ascending sorts an I4COL.
-
i4col_swap.m,
swaps two columns of an I4COL.
-
i4mat_print_some.m,
prints some of an I4MAT.
-
i4mat_transpose_print.m,
prints an I4MAT, transposed.
-
i4mat_transpose_print_some.m,
prints some of the transpose of an I4MAT.
-
i4vec_heap_d.m,
reorders an I4VEC into a descending heap.
-
i4vec_indicator.m,
sets an I4VEC to the vector A(I)=I.
-
i4vec_print.m,
prints an I4VEC.
-
i4vec_reverse.m,
reverses the elements of an I4VEC.
-
i4vec_sort_heap_a.m,
ascending sorts an I4VEC.
-
level_set.m,
generates the connected level structure rooted at a given node.
-
level_set_print.m,
prints level set information.
-
perm_check.m,
checks that a vector represents a permutation.
-
perm_inverse3.m,
produces the inverse of a given permutation.
-
perm_uniform.m,
selects a random permutation of N objects.
-
r82vec_permute.m,
permutes an R82VEC.
-
r8mat_print_some.m,
prints some of an R8MAT.
-
r8mat_transpose_print_some.m,
prints some of an R8MAT, transposed.
-
rcm.m,
renumbers a connected component by the reverse Cuthill McKee algorithm.
-
root_find.m,
finds a pseudo-peripheral node.
-
s_len_trim.m,
returns the length of a string to the last nonblank.
-
sort_heap_external.m,
externally sorts a list of items into ascending order.
-
triangulation_neighbor_triangles.m,
determines triangle neighbors.
-
triangulation_order3_adj_count.m,
counts adjacencies in a triangulation.
-
triangulation_order3_adj_set.m,
sets adjacencies in a triangulation.
-
triangulation_order3_example2.m,
returns an example triangulation.
-
triangulation_order3_example2_size.m,
returns the size of an example.
-
triangulation_order6_adj_count.m,
counts adjacencies in a triangulation.
-
triangulation_order6_adj_set.m,
sets adjacencies in a triangulation.
-
triangulation_order6_example2.m,
returns an example triangulation.
-
triangulation_order6_example2_size.m,
returns the size of an example.
Last revised on 17 September 2024.