TY - JOUR
T1 - Recursive spectral algorithms for automatic domain partitioning in parallel finite element analysis
AU - Hsieh, Shang Hsien
AU - Paulino, Glaucio H.
AU - Abel, John F.
N1 - Funding Information:
The writers wish to thank Dr. Horst D. Simon of NASA Ames ResearchC enter for kindly providing the source code of the RSB algorithm.T he supporto f NASA Lewis ResearchC enter under Grant No. NAG 3-1063h as been essentialt o this work and is appreciatedT. he partial support from the U.S. Air Force Office of ScientificR esearchu nder ContractN o. AFOSR-90-0211i s also appreciated.E quipment grants from both the Digital Equipment Corporation and Hewlett-Packardt o the Cornell Program of Computer Graphics are gratefully acknowledged.I n addition, Glaucio H. Paulino would like to acknowledge the financial support provided by the Brazilian Agency CNPq (National Council for Research and Development). Any opinions expressedh erein are those of the writers and do not necessarilyr eflect the views of the sponsorso r equipmentd onors.
PY - 1995/3
Y1 - 1995/3
N2 - Recently, several domain partitioning algorithms have been proposed to effect load-balancing among processors in parallel finite element analysis. The recursive spectral bisection (RSB) algorithm [1] has been shown to be effective. However, the bisection nature of the RSB results in partitions of an integer power of two, which is too restrictive for computing environments consisting of an arbitrary number of processors. This paper presents two recursive spectral partitioning algorithms, both of which generalize the RSB algorithm for an arbitrary number of partitions. These algorithms are based on a graph partitioning approach which includes spectral techniques and graph representation of finite element meshes. The 'algebraic connectivity vector' is introduced as a parameter to assess the quality of the partitioning results. Both node-based and element-based partitioning strategies are discussed. The spectral algorithms are also evaluated and compared for coarse-grained partitioning using different types of structures modelled by 1-D, 2-D and 3-D finite elements.
AB - Recently, several domain partitioning algorithms have been proposed to effect load-balancing among processors in parallel finite element analysis. The recursive spectral bisection (RSB) algorithm [1] has been shown to be effective. However, the bisection nature of the RSB results in partitions of an integer power of two, which is too restrictive for computing environments consisting of an arbitrary number of processors. This paper presents two recursive spectral partitioning algorithms, both of which generalize the RSB algorithm for an arbitrary number of partitions. These algorithms are based on a graph partitioning approach which includes spectral techniques and graph representation of finite element meshes. The 'algebraic connectivity vector' is introduced as a parameter to assess the quality of the partitioning results. Both node-based and element-based partitioning strategies are discussed. The spectral algorithms are also evaluated and compared for coarse-grained partitioning using different types of structures modelled by 1-D, 2-D and 3-D finite elements.
UR - http://www.scopus.com/inward/record.url?scp=0029276208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029276208&partnerID=8YFLogxK
U2 - 10.1016/0045-7825(94)00704-Q
DO - 10.1016/0045-7825(94)00704-Q
M3 - Article
AN - SCOPUS:0029276208
SN - 0045-7825
VL - 121
SP - 137
EP - 162
JO - Computer Methods in Applied Mechanics and Engineering
JF - Computer Methods in Applied Mechanics and Engineering
IS - 1-4
ER -