Title:
Domain decomposition methods--algorithms and theory
Personal Author:
Series:
Springer series in computational mathematics, 34
Publication Information:
Berlin : Springer, 2005
ISBN:
9783540206965
Added Author:
Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000004598383 | QA402.2 T67 2005 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
This book offers a comprehensive presentation of some of the most successful and popular domain decomposition preconditioners for finite and spectral element approximations of partial differential equations. It places strong emphasis on both algorithmic and mathematical aspects. It covers in detail important methods such as FETI and balancing Neumann-Neumann methods and algorithms for spectral element methods.
Table of Contents
1 Introduction | p. 1 |
1.1 Basic Ideas of Domain Decomposition | p. 1 |
1.2 Matrix and Vector Representations | p. 2 |
1.3 Nonoverlapping Methods | p. 5 |
1.3.1 An Equation for u¿: the Schur Complement System | p. 5 |
1.3.2 An Equation for the Flux | p. 6 |
1.3.3 The Dirichlet-Neumann Algorithm | p. 8 |
1.3.4 The Neumann-Neumann Algorithm | p. 10 |
1.3.5 A Dirichlet-Dirichlet Algorithm or a FETI Method | p. 12 |
1.3.6 The Case of Many Subdomains | p. 15 |
1.4 The Schwarz Alternating Method | p. 21 |
1.4.1 Description of the Method | p. 21 |
1.4.2 The Schwarz Alternating Method as a Richardson Method | p. 22 |
1.5 Block Jacobi Preconditioners | p. 24 |
1.6 Some Results on Schwarz Alternating Methods | p. 27 |
1.6.1 Analysis for the Case of Two Subdomains | p. 27 |
1.6.2 The Case of More than Two Subdomains | p. 29 |
2 Abstract Theory of Schwarz Methods | p. 35 |
2.1 Introduction | p. 35 |
2.2 Schwarz Methods | p. 35 |
2.3 Convergence Theory | p. 39 |
2.4 Historical Remarks | p. 46 |
2.5 Additional Results | p. 46 |
2.5.1 Coloring Techniques | p. 46 |
2.5.2 A Hybrid Method | p. 47 |
2.5.3 Comparison Results | p. 51 |
2.6 Remarks on the Implementation | p. 52 |
3 Two-Level Overlapping Methods | p. 55 |
3.1 Introduction | p. 55 |
3.2 Local Solvers | p. 56 |
3.3 A Coarse Problem | p. 59 |
3.4 Scaling and Quotient Space Arguments | p. 60 |
3.5 Technical Tools | p. 62 |
3.6 Convergence Results | p. 67 |
3.7 Remarks on the Implementation | p. 70 |
3.8 Numerical Results | p. 73 |
3.9 Restricted Schwarz Algorithms | p. 75 |
3.10 Alternative Coarse Problems | p. 75 |
3.10.1 Convergence Results | p. 76 |
3.10.2 Smoothed Aggregation Techniques | p. 81 |
3.10.3 Partition of Unity Coarse Spaces | p. 84 |
4 Substructuring Methods: Introduction | p. 87 |
4.1 Introduction | p. 87 |
4.2 Problem Setting and Geometry | p. 88 |
4.3 Schur Complement Systems | p. 94 |
4.4 Discrete Harmonic Extensions | p. 96 |
4.5 Condition Number of the Schur Complement | p. 97 |
4.6 Technical Tools | p. 99 |
4.6.1 Interpolation into Coarse Spaces | p. 99 |
4.6.2 Inequalities for Edges | p. 101 |
4.6.3 Inequalities for Faces | p. 105 |
4.6.4 Inequalities for Vertices and Auxiliary Results | p. 111 |
5 Primal Iterative Substructuring Methods | p. 113 |
5.1 Introduction | p. 113 |
5.2 Local Design and Analysis | p. 113 |
5.3 Local Solvers | p. 115 |
5.4 Coarse Spaces and Condition Number Estimates | p. 117 |
5.4.1 Vertex Based Methods | p. 118 |
5.4.2 Wire Basket Based Algorithms | p. 123 |
5.4.3 Face Based Algorithms | p. 126 |
6 Neumann-Neumann and FETI Methods | p. 131 |
6.1 Introduction | p. 131 |
6.2 Balancing Neumann-Neumann Methods | p. 133 |
6.2.1 Definition of the Algorithm | p. 133 |
6.2.2 Matrix Form of the Algorithm | p. 137 |
6.2.3 Condition Number Bounds | p. 139 |
6.3 One-Level FETI Methods | p. 143 |
6.3.1 A Review of the One-Level FETI Methods | p. 144 |
6.3.2 The Case of Nonredundant Lagrange Multipliers | p. 150 |
6.3.3 The Case of Redundant Lagrange Multipliers | p. 156 |
6.4 Dual-Primal FETI Methods | p. 160 |
6.4.1 FETI-DP Methods in Two Dimensions | p. 161 |
6.4.2 A Family of FETI-DP Algorithms in Three Dimensions | p. 167 |
6.4.3 Analysis of Three FETI-DP Algorithms | p. 175 |
6.4.4 Implementation of FETI-DP Methods | p. 185 |
6.4.5 Computational Results | p. 187 |
7 Spectral Element Methods | p. 193 |
7.1 Introduction | p. 193 |
7.2 Deville-Mund Preconditioners | p. 196 |
7.3 Two-Level Overlapping Schwarz Methods | p. 198 |
7.4 Iterative Substructuring Methods | p. 200 |
7.4.1 Technical Tools | p. 202 |
7.4.2 Algorithms and Condition Number Bounds | p. 206 |
7.5 Remarks on p and hp Approximations | p. 210 |
7.5.1 More General p Approximations | p. 210 |
7.5.2 Extensions to hp Approximations | p. 214 |
8 Linear Elasticity | p. 217 |
8.1 Introduction | p. 217 |
8.2 A Two-Level Overlapping Method | p. 219 |
8.3 Iterative Substructuring Methods | p. 220 |
8.4 A Wire Basket Based Method | p. 221 |
8.4.1 An Extension from the Interface | p. 222 |
8.4.2 An Extension from the Wire Basket | p. 222 |
8.4.3 A Wire Basket Preconditioner for Linear Elasticity | p. 224 |
8.5 Neumann-Neumann and FETI Methods | p. 225 |
8.5.1 A Neumann-Neumann Algorithm for Linear Elasticity | p. 225 |
8.5.2 One-Level FETI Algorithms for Linear Elasticity | p. 227 |
8.5.3 FETI-DP Algorithms for Linear Elasticity | p. 227 |
9 Preconditioners for Saddle Point Problems | p. 231 |
9.1 Introduction | p. 231 |
9.2 Block Preconditioners | p. 235 |
9.3 Flows in Porous Media | p. 239 |
9.3.1 Iterative Substructuring Methods | p. 241 |
9.3.2 Hybrid-Mixed Formulations and Spectral Equivalencies with Crouzeix-Raviart Approximations | p. 246 |
9.3.3 A Balancing Neumann-Neumann Method | p. 250 |
9.3.4 Overlapping Methods | p. 255 |
9.4 The Stokes Problem and Almost Incompressible Elasticity | p. 257 |
9.4.1 Block Preconditioners | p. 258 |
9.4.2 Iterative Substructuring Methods | p. 261 |
9.4.3 Computational Results | p. 269 |
10 Problems in H(div ; ¿) and H(curl; ¿) | p. 271 |
10.1 Overlapping Methods | p. 274 |
10.1.1 Problems in H(curl; ¿) | p. 276 |
10.1.2 Problems in H(div; ¿) | p. 283 |
10.1.3 Final Remarks on Overlapping Methods and Numerical Results | p. 286 |
10.2 Iterative Substructuring Methods | p. 288 |
10.2.1 Technical Tools | p. 291 |
10.2.2 A Face-Based Method | p. 299 |
10.2.3 A Neumann-Neumann Method | p. 301 |
10.2.4 Remarks on Two-Dimensional Problems and Numerical Results | p. 305 |
10.2.5 Iterative Substructuring for Nédélec Approximations in Three Dimensions | p. 308 |
11 Indefinite and Nonsymmetric Problems | p. 311 |
11.1 Introduction | p. 311 |
11.2 Algorithms on Overlapping Subregions | p. 314 |
11.3 An Iterative Substructuring Method | p. 320 |
11.4 Numerical Results | p. 321 |
11.4.1 A Nonsymmetric Problem | p. 322 |
11.4.2 The Helmholtz Equation | p. 324 |
11.4.3 A Variable-Coefficient, Nonsymmetric Indefinite Problem | p. 324 |
11.5 Additional Topics | p. 326 |
11.5.1 Convection-Diffusion Problems | p. 326 |
11.5.2 The Helmholtz Equation | p. 330 |
11.5.3 Optimized Interface Conditions | p. 333 |
11.5.4 Nonlinear and Eigenvalue Problems | p. 334 |
A Elliptic Problems and Sobolev Spaces | p. 337 |
A.1 Sobolev Spaces | p. 337 |
A.2 Trace Spaces | p. 341 |
A.3 Linear Operators | p. 343 |
A.4 Poincaré and Friedrichs Type Inequalities | p. 343 |
A.5 Spaces of Vector-Valued Functions | p. 346 |
A.5.1 The Space H(div; ¿) | p. 347 |
A.5.2 The Space H(curl; ¿) in Two Dimensions | p. 348 |
A.5.3 The Space H(curl; ¿) in Three Dimensions | p. 349 |
A.5.4 The Kernel and Range of the Curl and Divergence Operators | p. 350 |
A.6 Positive Definite Problems | p. 353 |
A.6.1 Scalar Problems | p. 355 |
A.6.2 Linear Elasticity | p. 357 |
A.6.3 Problems in H(div; ¿) and H(curl; ¿) | p. 360 |
A.7 Non-Symmetric and Indefinite Problems | p. 362 |
A.7.1 Generalizations of the Lax-Milgram Lemma | p. 362 |
A.7.2 Saddle-Point Problems | p. 364 |
A.8 Regularity Results | p. 369 |
B Galerkin Approximations | p. 371 |
B.1 Finite Element Approximations | p. 371 |
B.1.1 Triangulations | p. 371 |
B.1.2 Finite Element Spaces | p. 372 |
B.1.3 Symmetric, Positive Definite Problems | p. 374 |
B.1.4 Non-Symmetric and Indefinite Problems | p. 375 |
B.2 Spectral Element Approximations | p. 376 |
B.3 Divergence and Curl Conforming Finite Elements | p. 380 |
B.3.1 Raviart-Thomas Elements | p. 380 |
B.3.2 Nédélec Elements in Two Dimensions | p. 382 |
B.3.3 Nédélec Elements in Three Dimensions | p. 383 |
B.3.4 The Kernel and Range of the Curl and Divergence Operators | p. 384 |
B.4 Saddle-Point Problems | p. 386 |
B.4.1 Finite Element Approximations for the Stokes Problem | p. 387 |
B.4.2 Spectral Element Approximations for the Stokes Problem | p. 388 |
B.4.3 Finite Element Approximations for Flows in Porous Media | p. 389 |
B.5 Inverse Inequalities | p. 389 |
B.6 Matrix Representation and Condition Number | p. 390 |
C Solution of Algebraic Linear Systems | p. 395 |
C.1 Eigenvalues and Condition Number | p. 395 |
C.2 Direct Methods | p. 397 |
C.2.1 Factorizations | p. 397 |
C.2.2 Fill-in | p. 398 |
C.3 Richardson Method | p. 399 |
C.4 Steepest Descent | p. 402 |
C.5 Conjugate Gradient Method | p. 403 |
C.6 Methods for Non-Symmetric and Indefinite Systems | p. 407 |
C.6.1 The Generalized Minimal Residual Method | p. 407 |
C.6.2 The Conjugate Residual Method | p. 409 |
References | p. 413 |
Index | p. 447 |