TET_MESH_RCM
Reverse Cuthill-McKee Node Reordering

TET_MESH_RCM is a FORTRAN90 program which computes the reverse Cuthill-McKee reordering for nodes in a tetrahedral mesh ("tet mesh").

The user supplies a node file and a tetrahedron file, containing the coordinates of the nodes, and the indices of the nodes that make up each tetrahedron. Either 4-node or 10-node tetrahedrons may be used.

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 tetrahedrons, and writes out new node and tetrahedron files that correspond to the RCM permutation.

Note that the node file would normally contain exactly 3 values on each line, namely the X, Y and Z coordinates of the nodes. However, this is not necessary. Extra information can be included on each line, for instance, a "W" coordinate. Each line should include the same number of items, but all will be permuted correctly together. The program does not actually need to know the coordinates of the nodes, so in fact, ANY data (as long as it is real numeric data) associated with the nodes can be listed in the node file, and will be correctly permuted.

Usage:

tet_mesh_rcm node_file tetra_file

reads the tet mesh whose nodal coordinates are given in node_file, and tetrahedron indices in tetra_file, and produces a reordering of the nodes that will reduce the bandwidth.

Related Data and Programs:

CVT_TET_MESH is an executable FORTRAN90 program which uses CVT techniques to compute a tet mesh in a region.

MESH_BANDWIDTH is an interactive executable FORTRAN90 program which returns the geometric bandwidth associated with a mesh of elements of any order and in a space of arbitrary dimension.

RCM is a FORTRAN90 library of routines for reverse Cuthill-McKee computations.

TABLE_TET_MESH is an executable FORTRAN90 program which can compute the tet mesh for a given set of points.

TEST_TET_MESH is a FORTRAN90 library of routines defining regions for which a tet mesh is desired.

TET_MESH is a FORTRAN90 library of routines for working with tet meshes.

TET_MESH_DISPLAY is an executable MATLAB program which can read in the node and tetra files defining a tet mesh and display a wireframe image.

TET_MESH_DISPLAY_OPEN_GL is a C++ executable program which reads a tet mesh and displays the nodes and edges using OpenGL.

TET_MESH_L2Q is an executable FORTRAN90 program which converts a linear (4-node) to quadratic (10-node) tetrahedral mesh.

TET_MESH_ORDER4 is a directory which contains a description and examples of a tet mesh using order 4 elements.

TET_MESH_ORDER10 is a directory which contains a description and examples of a tet mesh using order 10 elements.

TET_MESH_Q2L is an executable FORTRAN90 program which converts a quadratic (10-node) to linear (4-node) tetrahedral mesh.

TET_MESH_QUALITY is an executable FORTRAN90 program which computes the quality of a tetrahedral mesh.

TET_MESH_RCM is also available in a C++ version and a MATLAB version.

TET_MESH_REFINE is an executable FORTRAN90 program which can refine a tet mesh.

TET_MESH_TET_NEIGHBORS is an executable FORTRAN90 program which computes the tetrahedral adjacency information.

TRIANGULATION_RCM is an executable FORTRAN90 program which applies the reverse Cuthill-McKee reordering to a triangulation of 2D data.

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. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   ISBN: 0-521-79309-2,
   LC: QA377.E36.
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, Number 2, April 1976, pages 236-250.
6. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, 1991, pages 325-331.
7. Per-Olof Persson, Gilbert Strang,
   A Simple Mesh Generator in MATLAB,
   SIAM Review,
   Volume 46, Number 2, June 2004, pages 329-345.

Source Code:

• tet_mesh_rcm.f90, the source code.
• tet_mesh_rcm.csh, commands to compile the source code.

Examples and Tests:

CUBE4 is an order 4 tet mesh of a cube:

• cube4_output.txt, the printed output from the command
  "tet_mesh_rcm cube4_nodes.txt cube4_tetras.txt"
• cube4_nodes.txt, the node file.
• cube4_tetras.txt, the tetrahedron file.
• cube4_nodes.rcm.txt, the RCM reordered node file.
• cube4_tetras.rcm.txt, the RCM reordered tetrahedron file.

CUBE4_EXTRA is a second version of the CUBE4 example, with two extra nodal data items at each node.

• cube4_extra_output.txt, the printed output from the command
  "tet_mesh_rcm cube4_nodes_extra.txt cube4_tetras.txt"
• cube4_nodes_extra.txt, the node file.
• cube4_tetras.txt, the tetrahedron file.
• cube4_nodes_extra.rcm.txt, the RCM reordered node file.
• cube4_tetras.rcm.txt, the RCM reordered tetrahedron file.

List of Routines:

• MAIN is the main program for TET_MESH_RCM.
• ADJ_BANDWIDTH computes the bandwidth of an adjacency matrix.
• ADJ_PERM_BANDWIDTH computes the bandwidth of a permuted adjacency matrix.
• ADJ_PRINT prints adjacency information.
• ADJ_PRINT_SOME prints some adjacency information.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DEGREE computes the degrees of the nodes in the connected component.
• DTABLE_DATA_READ reads data from a double precision table file.
• DTABLE_DATA_WRITE writes data to a double precision table file.
• DTABLE_HEADER_READ reads the header from a double precision table file.
• DTABLE_HEADER_WRITE writes the header to a double precision table file.
• DTABLE_WRITE writes a double precision table file.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_NAME_EXT_GET determines the "extension" of a file name.
• FILE_NAME_EXT_SWAP replaces the current "extension" of a file name.
• FILE_ROW_COUNT counts the number of row records in a file.
• GENRCM finds the reverse Cuthill-Mckee ordering for a general graph.
• GET_UNIT returns a free FORTRAN unit number.
• I4_SWAP swaps two integer values.
• I4COL_COMPARE compares columns I and J of an I4COL.
• I4COL_SORT_A ascending sorts an I4COL.
• I4COL_SORT2_A ascending sorts the elements of each column of an I4COL.
• I4COL_SORTED_UNIQUE_COUNT counts unique elements in an I4COL.
• I4COL_SWAP swaps columns J1 and J2 of an I4COL.
• 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 the rows of an I4ROW.
• I4ROW_SWAP swaps two rows of an I4ROW.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_REVERSE reverses the elements of an I4VEC.
• ITABLE_DATA_READ reads data from an integer table file.
• ITABLE_DATA_WRITE writes data to an integer table file.
• ITABLE_HEADER_READ reads the header from an integer table file.
• ITABLE_HEADER_WRITE writes the header to an integer table file.
• ITABLE_READ reads the information in an integer table file.
• ITABLE_WRITE writes an integer table file.
• LEVEL_SET generates the connected level structure rooted at a given node.
• PERM_CHECK checks that a vector represents a permutation.
• PERM_INVERSE3 produces the inverse of a given permutation.
• R8COL_PERMUTE permutes an R8COL in place.
• 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 pseudo-peripheral node.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_INDEX_LAST_C finds the LAST occurrence of a given character.
• S_TO_I4 reads an I4 from a string.
• S_TO_I4VEC reads an I4VEC from a string.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
• TET_MESH_ORDER4_ADJ_COUNT counts the number of nodal adjacencies.
• TET_MESH_ORDER4_ADJ_SET sets the nodal adjacency matrix.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING writes the current YMDHMS date into a string.

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