Gh. Paulino et al., NODE AND ELEMENT RESEQUENCING USING THE LAPLACIAN OF A FINITE-ELEMENTGRAPH .1. GENERAL CONCEPTS AND ALGORITHM, International journal for numerical methods in engineering, 37(9), 1994, pp. 1511-1530
A Finite Element Graph (FEG) is defined here as a nodal graph (G), a d
ual graph (G), or a communication graph (G.) associated with a generi
c finite element mesh. The Laplacian matrix ((L(G), L(G) or L(G.)), u
sed for the study of spectral properties of an FEG, is constructed fro
m usual vertex and edge connectivities of a graph. An automatic algori
thm, based on spectral properties of an FEG (G, G or G.), is proposed
to reorder the nodes and/or elements of the associated finite element
mesh. The new algorithm is called Spectral FEG Resequencing (SFR). Th
is algorithm uses global information in the graph, it does not depend
on a pseudoperipheral vertex in the resequencing process, and it does
not use any kind of level structure of the graph. Moreover, the SFR al
gorithm is of special advantage in computing environments with vector
and parallel processing capabilities. Nodes or elements in the mesh ca
n be reordered depending on the use of an adequate graph representatio
n associated with the mesh. If G is used, then the nodes in the mesh a
re properly reordered for achieving profile and wavefront reduction of
the finite element stiffness matrix. If either G or G. is used, then
the elements in the mesh are suitably reordered for a finite element
frontal solver. A unified approach involving FEGs and finite element c
oncepts is presented. Conclusions are inferred and possible extensions
of this research are pointed out. In Part II of this work,1 the compu
tational implementation of the SFR algorithm is described and several
numerical examples are presented. The examples emphasize important the
oretical, numerical and practical aspects of the new resequencing meth
od.