Parallel scalable iterative substructuring [Elektronische Ressource] : robust exact and inexact FETI-DP methods with applications to elasticity / Oliver Rheinbach

Parallel Scalable Iterative Substructuring:
Robust Exact and Inexact FETI-DP Methods
with Applications to Elasticity
Oliver Rheinbach
geboren in Hilden
Fachbereich Mathematik
Universit¨at Duisburg-Essen
29. Mai 2006
Dissertation im Fach Mathematik
zum Erwerb des Dr. rer. nat.
am Fachbereich Mathematik
der Universit¨at Duisburg-EssenErstgutachter: Prof. Dr. Axel Klawonn,
Fachbereich Mathematik, Universit¨at Duisburg-Essen
Zweitgutachter: Prof. Dr. Olof B. Widlund,
Courant Institute of Mathematical Sciences, New York University
Drittgutachter: Prof. Dr. Gerhard Starke,
Institut fur¨ Angewandte Mathematik, Universit¨at Hannover
Tag der mundlic¨ hen Prufung:¨ 13.07.2006Contents
1 Introduction 9
1.1 Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Scalar Partial Differential Equations (PDEs) . . . . . . . . . . 15
1.2.1 Weak Formulation and Ellipticity . . . . . . . . . . . . 15
1.2.2 Finite Element Method (FEM) . . . . . . . . . . . . . 16
1.3 Direct Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Krylov Subspace Methods . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Preconditioned Conjugate Gradient Method (PCG) . . 19
1.4.2 Generalized Minimal Residual Method (GMRES) . . . 20
1.5 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Discrete Harmonic Functions . . . . . . . . . . . . . . . . . . . 21
1/21.7 Equivalence of Schur Complement Norm and H (∂Ω)-Norm 22
1.8 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Two Iterative Substructuring Methods 25
2.1 A First Model Problem . . . . . . . . . . . . . . . . . . . . . . 28
2.2 FETI-DP and BDDC with Matrices and Vectors . . . . . . . . 30
2.2.1 FETI-DP Method . . . . . . . . . . . . . . . . . . . . . 31
2.2.2 BDDC Method . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Scaling for Heterogeneous Problems . . . . . . . . . . . . . . . 37
2.4 Convergence Estimate for FETI-DP and BDDC . . . . . . . . 38
3 FETI-DP for Linear Elasticity 49
3.1 Equations of Lineary . . . . . . . . . . . . . . . . . . 49
3.2 Need for an Appropriate Coarse Space . . . . . . . . . . . . . 53
3.3 FETI-DP in 3D . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.1 Change of Basis . . . . . . . . . . . . . . . . . . . . . . 56
3.3.2 Local Lagrange Multipliers . . . . . . . . . . . . . . . . 58
3.3.3 Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.4 Change of Basis for Edge Constraints . . . . . . . . . . 62
3.3.5 Choice of Coarse Problem . . . . . . . . . . . . . . . . 65
56 CONTENTS
3.3.6 Algorithm D . . . . . . . . . . . . . . . . . . . . . . . 70E
3.3.7 D . . . . . . . . . . . . . . . . . . . . . . . 71F
3.3.8 Optional Lagrange Multipliers . . . . . . . . . . . . . . 71
3.4 Parallel Implementation . . . . . . . . . . . . . . . . . . . . . 74
3.4.1 Distributed Computing and Message Passing . . . . . . 75
3.4.2 Graph Partitioning . . . . . . . . . . . . . . . . . . . . 76
3.4.3 PETSc . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.4.4 Parallel FETI-DP . . . . . . . . . . . . . . . . . . . . . 77
3.5 Numerical Results. . . . . . . . . . . . . . . . . . . . . . . . . 78
3.5.1 Model Problem . . . . . . . . . . . . . . . . . . . . . . 80
3.5.2 Industrial Applications . . . . . . . . . . . . . . . . . . 83
3.5.3 Cancellous Bone . . . . . . . . . . . . . . . . . . . . . 88
4 Inexact FETI-DP Methods 93
4.1 Saddle Point Formulation . . . . . . . . . . . . . . . 94
4.2 Exact and Inexact FETI-DP Methods. . . . . . . . . . . . . . 95
4.3 Block Triangular Preconditioners . . . . . . . . . . . . . . . . 97
4.4 Analysis of the . . . . . . . . . . . . . . . . . 100
4.4.1 Preconditioning the Original System (iFETI-DP) . . . 102
4.4.2 the Reduced (irFETI-DP). . . 103
4.5 Performance Considerations . . . . . . . . . . . . . . . . . . . 103
4.6 Some Technical Remarks . . . . . . . . . . . . . . . . . . . . . 104
4.7 Algebraic Multigrid (AMG) . . . . . . . . . . . . . . . . . . . 105
4.8 Numerical Results. . . . . . . . . . . . . . . . . . . . . . . . . 105
4.8.1 Direct Solvers . . . . . . . . . . . . . . . . . . . . . . . 105
4.8.2 Inexact Coarse Problem . . . . . . . . . . . . . . . . . 108
4.8.3 Neumann Problems . . . . . . . . . . . . . . . 111
4.8.4 Inexact Neumann, Dirichlet, and Coarse Problems . . . 114
4.9 Parallel Results . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5 Heterogeneous Elasticity 121
5.1 Additional Constraints . . . . . . . . . . . . . . . . . . . . . . 122
5.2 Necessary and Sufficient Constraints . . . . . . . . . . . . . . 124
5.3 Acceptable Paths . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.4 Curved Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.5 Heterogeneities Not Aligned With Interface . . . . . . . . . . . 137
5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143CONTENTS 7
6 Almost Incompressible Elasticity 145
6.1 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.2 Coarse Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.3 Numerical Results. . . . . . . . . . . . . . . . . . . . . . . . . 148
7 Higher Order Methods 151
7.1 Spectral Elements . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.1.1 Discretization . . . . . . . . . . . . . . . . . . . . . . . 152
7.1.2 Convergence Estimate . . . . . . . . . . . . . . . . . . 154
7.1.3 Numerical Results for FETI-DP and BDDC . . . . . . 155
7.2 hp Finite Elements . . . . . . . . . . . . . . . . . . . . . . . . 165
References 1708 CONTENTS
Acknowledgments
IwouldliketothankmyadvisorAxelKlawonnforthetimeandworkdevoted
to me and to this thesis as well as for the encouragement he gave me. I am
also grateful to Olof Widlund for inspiration and encouragement. I would
liketothankbothandGerhardStarkeforreviewingthiswork. Furthermore,
I am happy to thank my colleagues at the University of Duisburg-Essen,
especially Thomas Schamberg, with whom I have shared an office for many
years. I would not have been able to finish this work without the support of
my parents and my friends.
I am thankful for many fruitful discussions with Barry Smith, Satish
Balay, Matthew Knepley, Jason Sarich and the PETSc team, while visiting
the Mathematics and Computer Science Division at Argonne National Lab-
oratory, USA. I would also like to thank Panayot Vassilevski, Ulrike Meier
Yang, the hypre team and David Keyes at Lawrence Livermore National
Laboratory.
I am very happy to express my thanks to Barbara Wohlmuth and Luca
Pavarino as well as Andrea Toselli and Xavier Vasseur. I enjoyed working
with them.
I am grateful to Tanja Clees, Klaus Stub¨ en, and the Fraunhofer Institute
forAlgorithmsandScientificComputing(SCAI),SanktAugustin, Germany,
forprovidingSAMGandalsowishtothankHans-Jurgen¨ Philipsenburg,Hol-
ger Hein and GETRAG FORD Transmissions GmbH, Cologne, Germany.
This work gratefully acknowledges the X-ray computer tomography cross
sections which were obtained from Matthias Epple, Institute of Inorganic
Chemistry,UniversityofDuisburg-Essen, withinacommonresearchcollabo-
ration. Furthermore,thisworkgratefullyacknowledgestheuseofJazz,a350
nodecomputingclusteroperatedbytheMathematicsandComputerScience
Division at Argonne National Laboratory, USA, as part of its Laboratory
Computing Resource Center. It also gratefully acknowledges the use of the
2304processorMCRclusterattheLawrenceLivermoreNationalLaboratory,
USA. Moreover, for this work computing time was used on the 96 processor
Zivcluster of the Universit¨at Munster,¨ Germany, as part of the Rechnerver-
bund NRW. Additional testing was done, to some extent, on the 256 proces-
sor Rubens cluster of the Universit¨at Siegen, the 1024 processor ALiCEnext
cluster of the Universit¨at Wuppertal, and on our own 16 processor cluster in
Essen. Many images in this work were rendered using Medit [48].Chapter 1
Introduction
Many complex problems in physics and engineering are described by Partial
Differential Equations (PDEs). In general, it is impossible to find exact so-
lutions to these equations, and instead a discrete problem is defined, which
represents an approximation of the original problem. Such a discrete prob-
lem can be defined, e.g., by using the finite element method (FEM). The
discretization then results in large linear equation systems, which today can
5 9be of the order of 10 to 10 unknowns. These linear systems are often too
largetobesolvedexactly. Domaindecompositionmethodsareiterativealgo-
rithms to find approximate solutions for the large systems obtained from the
discretizationofPartialDifferentialEquations. Theymakeuseofunderlying
propertiesofthePDEstoachievefastconvergencebyapplyingahierarchical
approach. In domain decomposition methods, the domain associated with
the partial differentialequation is decomposed into a, possibly large, number
of subdomains. In these subdomains, local problems are defined, which are
solved in each iteration step in order to define an approximate inverse of the
system matrix. In order to obtain a numerical scalable algorithm, also a
small coarse problem has to be introduced a