TY - JOUR

T1 - Node and element resequencing using the Laplacian of a finite element graph

T2 - Part I—General concepts and algorithm

AU - Paulino, Glaucio H.

AU - Menezes, Ivan F.M.

AU - Gattass, Marcelo

AU - Mukherjee, Subrata

PY - 1994/5/15

Y1 - 1994/5/15

N2 - A Finite Element Graph (FEG) is defined here as a nodal graph (G), a dual graph (G*), or a communication graph (G˙) associated with a generic finite element mesh. The Laplacian matrix (L(G),L(G*) or L(G˙)), used for the study of spectral properties of an FEG, is constructed from usual vertex and edge connectivities of a graph. An automatic algorithm, 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 PEG Resequencing (SFR). This 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 algorithm is of special advantage in computing environments with vector and parallel processing capabilities. Nodes or elements in the mesh can be reordered depending on the use of an adequate graph representation associated with the mesh. If G is used, then the nodes in the mesh are 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 frontai solver, A unified approach involving FEGs and finite element concepts is presented. Conclusions are inferred and possible extensions of this research are pointed out. In Part II of this work,1 the computational implementation of the SFR algorithm is described and several numerical examples are presented. The examples emphasize important theoretical, numerical and practical aspects of the new resequencing method.

AB - A Finite Element Graph (FEG) is defined here as a nodal graph (G), a dual graph (G*), or a communication graph (G˙) associated with a generic finite element mesh. The Laplacian matrix (L(G),L(G*) or L(G˙)), used for the study of spectral properties of an FEG, is constructed from usual vertex and edge connectivities of a graph. An automatic algorithm, 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 PEG Resequencing (SFR). This 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 algorithm is of special advantage in computing environments with vector and parallel processing capabilities. Nodes or elements in the mesh can be reordered depending on the use of an adequate graph representation associated with the mesh. If G is used, then the nodes in the mesh are 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 frontai solver, A unified approach involving FEGs and finite element concepts is presented. Conclusions are inferred and possible extensions of this research are pointed out. In Part II of this work,1 the computational implementation of the SFR algorithm is described and several numerical examples are presented. The examples emphasize important theoretical, numerical and practical aspects of the new resequencing method.

UR - http://www.scopus.com/inward/record.url?scp=0028436709&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028436709&partnerID=8YFLogxK

U2 - 10.1002/nme.1620370907

DO - 10.1002/nme.1620370907

M3 - Article

AN - SCOPUS:0028436709

VL - 37

SP - 1511

EP - 1530

JO - International Journal for Numerical Methods in Engineering

JF - International Journal for Numerical Methods in Engineering

SN - 0029-5981

IS - 9

ER -