MESH_BANDWIDTH Geometric Bandwidth of a Mesh

MESH_BANDWIDTH is a C program 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
where ML is the lower bandwidth, namely, the maximum value over all nodes I of the difference (I-J), taken over all nodes J that share an element with node I. The upper bandwidth is the maximum value of (J-I) under the same conditions.

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.

Usage:

mesh_bandwidth element_file
where
• element_file contains a list of the node indices that form each triangle of the triangulation,
computes and prints the geometric bandwidth.

Languages:

MESH_BANDWIDTH is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

TABLE_DELAUNAY, a C++ program which triangulates a set of nodes whose coordinates are stored in a file.

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

TRIANGLE, a C program which computes a triangulation of a geometric region.

TRIANGULATION_BOUNDARY_NODES, a C++ program which reads data defining a triangulation, determines which nodes lie on the boundary, and writes their coordinates to a file.

TRIANGULATION_DISPLAY_OPENGL, a C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_L2Q, a C++ program which reads data defining a 3-node triangulation and generates midside nodes and writes out the corresponding 6-node triangulation.

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_ORIENT, a C++ program which reads data defining a triangulation, makes sure that every triangle has positive orientation, and if not, writes a corrected triangle file.

TRIANGULATION_PLOT, a C++ program which reads data defining a triangulation and creates a PostScript image of the nodes and triangles.

TRIANGULATION_Q2L, a C++ program which 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, a C++ program which reads data defining a triangulation and computes a number of quality measures.

TRIANGULATION_REFINE, a C++ program which can be used to refine a triangulation.

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.

Examples and Tests:

Some sample mesh files include:

List of Routines:

• MAIN is the main program for MESH_BANDWIDTH.
• BANDWIDTH_MESH determines the bandwidth of the coefficient matrix.
• 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.
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the smaller of two I4's.