A multi-level finite element nodal ordering using algebraic graph theory

In this paper an efficient method is developed for nodal and element ordering of structures and finite element models. The present method is based on concepts from algebraic graph theory and comprises of an efficient algorithm for calculating the Fiedler vector of the Laplacian matrix of a graph. The problem of finding the second eigenvalue of the Laplacian matrix is transformed into evaluating the maximal eigenvalue of the complementary Laplacian matrix. An iterative method is then employed to form the eigenvector needed for renumbering the vertices of a graph. An appropriate transformation, maps the vertex ordering of graphs into nodal and element ordering of the finite element models. In order to increase the efficiency of the algebraic graph theoretical method, a multi-level scheme is adopted in which the graph model corresponding to a finite element mesh is coarsened in various levels to reduce the size of the problem. Then an efficient algebraic method is applied and with an uncoarsening process, the final ordering of the graph and hence that of the corresponding finite element model is obtained. (C) 2002 Elsevier Science B.V. All rights reserved.