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

被引:20
作者
Kaveh, A [1 ]
Bondarabady, HAR
机构
[1] Iran Univ Sci & Technol, Dept Civil Engn, Struct & Hydrostruct Res Ctr, Tehran 16, Iran
[2] Univ Yazd, Yazd, Iran
关键词
finite element; nodal ordering; graph theory; algebraic graph theory; coarsening; Laplacian; complementary Laplacian; eigensolution;
D O I
10.1016/S0168-874X(01)00062-2
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:245 / 261
页数:17
相关论文
共 24 条
  • [1] [Anonymous], 1995, STRUCTURAL MECH GRAP
  • [2] Biggs N., 1993, ALGEBRAIC GRAPH THEO
  • [3] Bui T., 1993, 6 SIAM C PAR PROC SC, P445
  • [4] CHUNG JJ, 1997, CBMS, V92
  • [5] CVELKOVIC DM, 1980, SPECTRA GRAPHS THEOR
  • [6] Cvetkovic D., 2005, GRAPH THEORY COMBINA, V131, P85
  • [7] ERVERSTINE GC, 1979, INT J NUMER METHS EN, V14, P837
  • [8] FIEDLER M, 1973, CZECH MATH J, V23, P298
  • [9] Gould Peter., 1967, I BRIT GEOGRAPHERS T, V42, P53, DOI DOI 10.2307/621372
  • [10] A NEW ALGORITHM FOR FINDING A PSEUDOPERIPHERAL NODE IN A GRAPH
    GRIMES, RG
    PIERCE, DJ
    SIMON, HD
    [J]. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1990, 11 (02) : 323 - 334