Domain Decomposition Methods

by Toselli, Andrea; Widlund, Olof B.

• ISBN13: 9783540206965
• ISBN10: 3540206965
• Format: Hardcover
• Copyright: 2004-09-30
• Publisher: Springer Nature

Summary

The purpose of this text is to offer a comprehensive and self-contained presentation of some of the most successful and popular domain decomposition preconditioners for finite and spectral element approximations of partial differential equations. Strong emphasis is placed on both algorithmic and mathematical aspects. Some important methods such FETI and balancing Neumann-Neumann methods and algorithms for spectral element methods, not treated previously in any monograph, are covered in detail.Winner of the 2005 Award for Excellence in Professional and Scholarly Publishing - Mathematics/Statistics - of the Association of American Publishers

Table of Contents

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