Domain decomposition methods--algorithms and theory

Title:

Personal Author:

Toselli, Andrea

Series:

Springer series in computational mathematics, 34

Publication Information:

Berlin : Springer, 2005

ISBN:

9783540206965

Subject Term:

Decomposition method

Differential equations, Partial

Added Author:

Widlund, Olof B

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000004598383	QA402.2 T67 2005	Open Access Book	Book	Searching... Unknown

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.

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

Available:*

On Order

Summary

Summary

Table of Contents