Three widely-used nodal resequencing algorithms were tested and compared for their ability to reduce matrix profile and root-mean-square (rms) wavefront, the latter being the most critical parameter in determining matrix decomposition time in the NASTRAN finite element computer program. The three algorithms are Cuthill-McKee (CM), Gibbs-Poole-Stockmeyer (GPS), and Levy. Results are presented for a diversified collection of 30 test problems ranging in size from 59 to 2680 nodes. It is concluded that GPS is exceptionally fast, and, for the conditions under which the test was made, the algorithm best able to reduce profile and rms wavefront consistently well. An extensive bibliography of resequencing algorithms is included.
BACKGROUND
Many problems of scientific and engineering interest reduce to the numerical problem of solving a large set of linear algebraic equations such as, in matrix form,
A x = b
(1)
where the vector b and the square matrix A are known, and the unknown vector x is sought. In finite element and other applications, A is also sparsely populated (i.e., it contains far more zeros than non-zeros), since the procedure under which finite element matrices are assembled dictates that the off-diagonal matrix terms coupling any two degrees-of-freedom are zero unless those degrees-of-freedom are common to the same finite element."* It also follows that the locations of the non-zero elements of the matrix A depend solely on the ordering of the unknowns. In finite element applications, for example, the ordering of the unknowns corresponds to the selection of grid point (or nodal) numbers for the mesh points. Thus, it is possible with sparse matrices to choose an ordering which results in the non-zeros being located in a way convenient for subsequent matrix operations such as equation solving or eigenvalue extraction.
A good ordering is essential to the finite element user since virtually all finite element computer programs contain equation solution and eigenvalue routines which have been expressly written to operate efficiently on matrices possessing small bandwidth, profile, or wavefront. Efficiency is obtained by avoiding arithmetic operations on matrix elements known to be zero. The execution time for a 'band solver,' for example, is O(NB2) for large N and B, where N is the matrix order and B the bandwidth. For a given finite element model, N is fixed, but B depends on the ordering of the unknowns (grid points). Clearly, in this case, it is desirable to reduce B as much as possible.