QUAD_MESH_RCM
Reverse Cuthill-McKee Node Reordering

QUAD_MESH_RCM is a MATLAB program which computes the reverse Cuthill-McKee (RCM) reordering for nodes in a mesh of 4-node quadrilaterals.

The user supplies a node file and an element file, containing the coordinates of the nodes, and the indices of the nodes that make up each element.

The program reads the data, computes the adjacency information, carries out the RCM algorithm to get the permutation, applies the permutation to the nodes and elements, and writes out new node and element files that correspond to the RCM permutation.

Usage:

quad_mesh_rcm 'prefix'

• 'prefix'_nodes.txt, the node coordinates;
• 'prefix'_elements.txt, the element definitions.
• 'prefix'_rcm_nodes.txt, the reordered node coordinates;
• 'prefix'_rcm_elements.txt, the reordered element definitions.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

QUAD_MESH_RCM is available in a C++ version and a FORTRAN version and a MATLAB version.

Related Data and Programs:

MESH_BANDWIDTH, a MATLAB program which returns the geometric bandwidth associated with a mesh of elements of any order and in a space of arbitrary dimension.

MESH_DISPLAY, a MATLAB program which reads data defining a polygonal mesh and displays it, with optional numbering.

MESH_DISPLAY_OPENGL, a C++ program which reads files defining a polygonal mesh and displays an image using OpenGL.

QUAD_MESH, a data directory which defines a format for storing meshes of quadrilaterals over a 2D region.

QUAD_MESH, a MATLAB library which handles meshes of quadrilaterals over a 2D region;

RCM, a MATLAB library which carries out reverse Cuthill-McKee computations.

TET_MESH_RCM, a MATLAB program which applies the reverse Cuthill-McKee reordering to a tetrahedral mesh of nodes in 3D.

TRIANGULATION_RCM, a MATLAB 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:

1. 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.
2. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0.
3. Alan George, Joseph Liu,
   Computer Solution of Large Sparse Positive Definite Matrices,
   Prentice Hall, 1981,
   ISBN: 0131652745,
   LC: QA188.G46
4. Norman Gibbs,
   Algorithm 509: A Hybrid Profile Reduction Algorithm,
   ACM Transactions on Mathematical Software,
   Volume 2, Number 4, December 1976, pages 378-387.
5. 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, 1976, pages 236-250.
6. Joseph ORourke,
   Computational Geometry,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.

Source Code:

• quad_mesh_rcm.m, the source code.

Examples and Tests:

HOLE works with region of equal-sized squares, with some irregularities.

• hole_output.txt, the printed output from the command
  "quad_mesh_rcm ( 'hole' )"
• hole_nodes.txt, the node file.
• hole_elements.txt, the element file.
• hole_rcm_nodes.txt, the RCM reordered node file.
• hole_rcm_elements.txt, the RCM reordered element file.
• hole.png, an image of the mesh.

You can go up one level to the MATLAB source codes.