MESH_BANDWIDTH
Geometric Bandwidth of a Mesh

MESH_BANDWIDTH is a FORTRAN90 program, using double precision arithmetic, which computes the geometric bandwidth of a mesh.

The user specifies an element file, containing the indices of the nodes that make up each element. Examples of such a file include the order 3 and order 6 triangulation files, but any order of element may be used.

Not only may any element type be used, but the geometric region may be of any spatial dimension.

The program reads the element information and computes the geometric bandwidth M as

M = ML + 1 + MU

The geometric bandwidth M is the linear algebraic bandwidth of the adjacency matrix of the mesh, where I and J are considered to be adjacent if there is some element that includes both nodes.

The geometric bandwidth is of interest since it is the bandwidth of the finite element matrix associated with the mesh, when a scalar quantity is being approximated and there is a single unknown for every node, and the unknowns have the same numbering as the nodes.

Related Data and Programs:

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

TABLE_DELAUNAY is an executable FORTRAN90 program for the triangulation of a set of nodes whose coordinates are stored in a file.

TET_MESH_RCM is an executable FORTRAN90 program which applies the reverse Cuthill-McKee reordering to a tetrahedral mesh of nodes in 3D.

TRIANGLE is an executable C program which computes a triangulation of a geometric region.

TRIANGULATION_BOUNDARY_NODES is an executable FORTRAN90 program that reads data defining a triangulation, determines which nodes lie on the boundary, and writes their coordinates to a file.

TRIANGULATION_DISPLAY_OPEN_GL is an executable C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_L2Q is an executable FORTRAN90 program that reads data defining a 3-node triangulation and generates midside nodes and writes out the corresponding 6-node triangulation.

TRIANGULATION_ORDER3 is a directory which contains a description and examples of order 3 triangulations.

TRIANGULATION_ORDER6 is a directory which contains a description and examples of order 6 triangulations.

TRIANGULATION_ORIENT is an executable FORTRAN90 program that reads data defining a triangulation, makes sure that every triangle has positive orientation, and if not, writes a corrected triangle file.

TRIANGULATION_PLOT is an executable FORTRAN90 program that reads data defining a triangulation and creates a PostScript image of the nodes and triangles.

TRIANGULATION_Q2L is an executable FORTRAN90 program that reads data defining a 6-node triangulation, and subdivides each triangle into 4 3-node triangles, writing the resulting triangulation to a file.

TRIANGULATION_QUALITY is an executable FORTRAN90 program that reads data defining a triangulation and computes a number of quality measures.

TRIANGULATION_REFINE is an executable FORTRAN90 program which can be used to refine a triangulation.

Usage:

mesh_bandwidth element_file

reads the mesh whose node indices are in element_file, and computes the geometric bandwidth.

Reference:

1. Alan George, Joseph Liu,
   Computer Solution of Large Sparse Positive Definite Matrices,
   Prentice Hall, 1981,
   QA 188.G46
2. 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, pages 236-250, 1976.
3. Norman Gibbs,
   Algorithm 509: A Hybrid Profile Reduction Algorithm,
   ACM Transactions on Mathematical Software,
   Volume 2, Issue 4, pages 378-387, 1976.
4. Joseph ORourke,
   Computational Geometry,
   Cambridge University Press,
   Second Edition, 1998.

Source Code:

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

Examples and Tests:

• mesh_bandwidth_prb.csh, a script that runs the program on a number of meshes.
• mesh_bandwidth_prb_output.txt, the resulting output.

Some sample mesh files include:

• sphere_q4_elements.txt
• sphere_t3_elements.txt
• cube_order4_tetras.txt
• twenty_order4_tetras.txt
• cube_order10_tetras.txt
• oneoneeight_order10_tetras.txt
• ell_tri3.txt
• hex_cvt_tri3.txt
• hex_triangle_tri3.txt
• hot_pipe_tri3.txt
• ell_tri6.txt
• hex_jeff_tri6.txt

List of Routines:

• MAIN is the main program for MESH_BANDWIDTH.
• BANDWIDTH determines the bandwidth associated with the finite element mesh.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_ROW_COUNT counts the number of row records in a file.
• GET_UNIT returns a free FORTRAN unit number.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• ITABLE_DATA_READ reads data from an integer table file.
• ITABLE_HEADER_READ reads the header from an integer table file.
• S_TO_I4 reads an I4 from a string.
• S_TO_I4VEC reads an I4VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• 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.