Domain Decomposition Methods in Science and Engineering XVIII (eBook)

Michel Bercovier, Martin Gander, Ralf Kornhuber, Olof Widlund (Herausgeber)

eBook Download: PDF

2009
XVI, 376 Seiten
Springer Berlin (Verlag)
978-3-642-02677-5 (ISBN)

Infos

th This volume contains a selection of 41 refereed papers presented at the 18 International Conference of Domain Decomposition Methods hosted by the School of ComputerScience and Engineering(CSE) of the Hebrew Universityof Jerusalem, Israel, January 12-17, 2008. 1 Background of the Conference Series The International Conference on Domain Decomposition Methods has been held in twelve countries throughout Asia, Europe, the Middle East, and North America, beginning in Paris in 1987. Originally held annually, it is now spaced at roughly 18-month intervals. A complete list of past meetings appears below. The principal technical content of the conference has always been mathematical, but the principal motivation has been to make ef cient use of distributed memory computers for complex applications arising in science and engineering. The leading 15 such computers, at the 'petascale' characterized by 10 oating point operations per second of processing power and as many Bytes of application-addressablem- ory, now marshal more than 200,000 independentprocessor cores, and systems with many millions of cores are expected soon. There is essentially no alternative to - main decomposition as a stratagem for parallelization at such scales. Contributions from mathematicians, computerscientists, engineers,and scientists are together n- essary in addressing the challenge of scale, and all are important to this conference.

Inhalt

Preface 5
Contents 13
Part I Plenary Presentations 17
A Domain Decomposition Approach for Calculating the GraphCorresponding to a Fibrous Geometry 18
1 Introduction 18
2 Preliminaries 19
3 Statement of the Problem 20
4 A Divide and Conquer Algorithm 20
4.1 Numerical Complexity of Algorithm 1 21
5 Numerical Results and Conclusions 23
References 29
Adaptive Multilevel Interior-Point Methods in PDE ConstrainedOptimization 30
1 Introduction 30
2 Optimal Design of Processes and Systems 31
3 Adaptive Multilevel Primal-Dual Interior Point Methods 32
4 Numerical Results 36
References 39
Numerical Homogeneisation Technique with Domain DecompositionBased a-posteriori Error Estimates 42
1 Introduction 42
2 Mechanical Problem 43
3 Numerical Homogeneisation 44
4 Error Control 45
4.1 Motivation and Reference Local Solution 45
4.2 Adjoint Equation 47
4.3 Explicit a Posteriori Error Estimate 48
4.4 Numerical Solution of the Adjoint Problem 49
5 Numerical Results 49
6 Conclusions 51
References 51
Multiscale Methods for Multiphase Flow in Porous Media 53
1 Introduction 53
2 A Framework for Discussing Multiscale Methods 54
3 A Model Problem for Multiphase Flow 55
4 Some Upscaling Methods 56
4.1 Permeability Upscaling 56
4.2 Saturation Upscaling 58
4.3 Vertically Integrated Models 59
5 Multiscale Numerical Methods 60
5.1 The Variational Multiscale Method 60
5.2 A VMS Approach for the Implicit Time-Discretized Pressure Equation 61
6 Conclusions 62
References 62
Mixed Plane Wave Discontinuous Galerkin Methods 65
1 Introduction 65
2 Mixed Discontinuous Galerkin Approach 66
3 Convergence Analysis of the Mixed PWDG Method 68
4 Conclusion 75
References 75
Numerical Zoom and the Schwarz Algorithm 77
1 Introduction 77
Chimera 77
Hilbert Space Decomposition Method 78
Harmonic Patch Iterator 79
One Way Schwarz 80
2 Convergence of Schwarz' Algorithm on Arbitrary Non-Matching Meshes 81
Numerical Tests 84
3 Numerical Comparison of the Methods 85
4 Conclusion 87
References 87
BDDC for Nonsymmetric Positive Definite and Symmetric IndefiniteProblems 88
1 Introduction 88
2 Finite Element Discretization 89
2.1 Nonsymmetric, Positive Definite Problems 89
2.2 Symmetric, Indefinite Problems 90
3 The BDDC Preconditioners 91
4 Convergence Rate Analysis 92
4.1 Nonsymmetric, Positive Cases 93
4.2 Symmetric, Indefinite Cases 94
5 Numerical Experiments 95
5.1 Nonsymmetric, Positive Definite Cases 95
5.2 Symmetric and Indefinite Cases 95
References 98
Accomodating Irregular Subdomains in Domain Decomposition Theory 100
1 Introduction 100
2 A Poincaré Inequality, John and Jones Domains 102
3 FETI-DP and BDDC Algorithms 104
4 An Overlapping Schwarz Method 107
5 Almost Incompressible Elasticity 109
References 110
Auxiliary Space Preconditioners for Mixed Finite Element Methods 112
1 Introduction 112
2 HX-Preconditioner for H(div) Systems 113
3 Application to Mixed Method 116
4 Numerical Results 118
4.1 Constant Coefficients 118
4.2 Variable Coefficients 118
4.3 Augmented Lagrangian Iterations 120
5 Conclusions 121
References 121
Part II Minisymposia 123
A Multilevel Domain Decomposition Solver Suited to NonsmoothMechanical Problems 124
1 Introduction 124
2 A Multiscale Description 124
3 Preliminary: Linear Elastic Case 125
4 Nonsmooth Case: a Tensegrity Grid 128
5 Conclusions 130
References 130
A FETI-2LM Method for Non-Matching Grids 132
1 Introduction 132
2 FETI-2LM method 132
2.1 Discrete Approach 132
2.2 Optimal Interface Operator 134
3 Mortar Method 135
4 A FETI-2LM Method for Non-conforming Interfaces 136
5 Localization of Non-conforming Interface Matching Conditions 137
6 Conclusion 138
References 139
Truncated Nonsmooth Newton Multigrid Methods for ConvexMinimization Problems 140
1 Introduction 140
2 A Nonsmooth Newton Method 141
3 Multigrid 143
4 Example I: Two-Body Contact in Linear Elasticity 144
5 Example II: The Allen-Cahn Equation 145
References 147
A Recursive Trust-Region Method for Non-Convex ConstrainedMinimization 148
1 Introduction 148
2 The Multilevel Setting 149
3 Recursive Trust-Region Methods 150
3.1 Convergence to First-Order Critical Points 151
4 Numerical Example 154
References 154
A Robin Domain Decomposition Algorithm for Contact Problems:Convergence Results 156
1 Introduction 156
2 Weak Formulation of the Continuous Problem 156
3 The Domain Decomposition Algorithm 158
4 Convergence 159
5 Numerical Experiments 161
References 162
Patch Smoothers for Saddle Point Problems with Applicationsto PDE-Constrained Optimization Problems 164
1 Introduction 164
2 An Optimal Control Problem 165
3 The Multigrid Method 167
3.1 The Patch Smoother 168
4 Numerical Experiments 169
References 171
A Domain Decomposition Preconditioner of Neumann-NeumannType for the Stokes Equations 172
1 Introduction 172
2 DDM for the Stokes Equations 173
2.1 Stokes Equations 173
2.2 A New Algorithm for the Stokes Equations 173
3 Numerical Results 174
References 178
Non-overlapping Domain Decomposition for the Richards Equationvia Superposition Operators 180
1 Introduction 180
2 Weak Forms of the Domain Decomposition Problems 182
3 Kirchhoff Transformation as a Superposition Operator 183
4 Equivalence of the Weak Formulations 186
References 187
Convergence Behavior of a Two-Level Optimized Schwarz Preconditioner 188
1 Introduction 188
2 Domain Decomposition Preconditioners 189
2.1 One-Level Preconditioners 189
2.2 Interpretation of the Algebraic Condition 190
2.3 Two-Level Preconditioners 191
3 Numerical Results 192
3.1 Dependence on h 192
3.2 Dependence on H, with Generous Overlap 193
3.3 A Weak Scalability Test 193
4 Best Robin Parameter 193
References 195
An Algorithm for Non-Matching Grid Projections with Linear Complexity 196
1 Introduction 196
2 Towards an Optimal Algorithm 196
3 The Algorithm for Computing the Intersection 198
4 The Projection Algorithm with Linear Complexity 199
5 Numerical Experiments 201
6 Conclusions 201
References 202
A Maximum Principle for L2-Trace Norms withan Application to Optimized Schwarz Methods 204
1 Introduction 204
2 The Maximum Principle for L2-Trace Norms 205
2.1 Preliminaries on the Domain and the Interfaces 205
2.2 (,a,c)-Harmonicity 206
2.3 -Relative Uniformity 207
2.4 Maximum Principle for L2-Trace Norms 208
3 Applications to Schwarz Methods 210
References 211
An Extended Mathematical Framework for Barrier Methodsin Function Space 212
1 Convex State Constrained Optimal Control 212
1.1 Linear Equality Constraints 213
1.2 Inequality Constraints and Convex Functionals 213
1.3 Example: A class of Elliptic PDEs 214
2 The Homotopy Path and its Properties 215
References 219
Optimized Schwarz Preconditioning for SEM BasedMagnetohydrodynamics 220
1 Introduction 220
2 Governing Equations and Discretization 221
3 From Classical to Optimized Schwarz 223
4 Discretization of the Optimized Schwarz 224
5 Numerical Experiments 226
References 227
Nonlinear Overlapping Domain Decomposition Methods 228
1 Introduction 228
2 Newton-Krylov-Schwarz Algorithms 230
3 Classical Schwarz Alternating Algorithms 231
4 Nonlinear Additive Schwarz Preconditioned Inexact Newton Algorithms 231
5 Nonlinear Elimination Algorithms 232
6 Nonlinear Restricted Additive Schwarz Algorithms 233
7 Concluding Remarks 234
References 235
Optimized Schwarz Waveform Relaxation: Roots, Blossoms and Fruits 236
1 Introduction: Parallel Processing of Evolution Problems 236
2 Roots: Waveform Relaxation for ODEs 237
3 Blossoms: Classical Schwarz Waveform Relaxation for Parabolic Equations 238
4 Fruits: Optimized Schwarz Waveform Relaxationfor Parabolic Equations 239
5 Other Fruits: Optimized Schwarz Waveform Relaxationfor Other Types of PDEs 240
6 New Blossoms: Space-Time Coupling and Refinements 241
References 242
Optimized Schwarz Methods 244
1 Introduction: Original Schwarz Method (1870) 244
1.1 Towards Faster Methods: Two Families of Methods 245
2 Modified Schwarz Method 246
2.1 Generalized Schwarz Methods 246
2.2 Optimal Interface Conditions 247
3 Conclusion and Open Problems 249
References 249
The Development of Coarse Spaces for DomainDecomposition Algorithms 252
1 Introduction 252
2 Early Two-Level Domain Decomposition Methods 253
3 Additional Comments 255
4 Other Iterative Substructuring Methods 255
5 FETI-DP and BDDC 256
6 Additional Roles for Coarse Spaces 257
References 257
Part III Contributed Presentations 260
Distributed Decomposition Over Hyperspherical Domains 261
1 Global Optimization for Semiconductor LithographyMask Design 261
1.1 Convex Partitions of the Feasible Domain 262
2 Partitions of n-Space 263
3 Incomplete Search Heuristics 263
4 Hypersphere Decomposition 264
4.1 Previous Work 264
4.2 A Memory-Efficient Tree Storage Scheme for Equal AreaHypersphere Regions 265
4.3 Parallel Decomposition 266
5 Ongoing Work 267
References 267
Domain Decomposition Preconditioning for Discontinuous GalerkinApproximations of Convection-Diffusion Problems 269
1 Introduction 269
2 Statement of the Problem and its DG Approximation 269
3 Nonoverlapping Schwarz Methods 271
4 The Issue of Convergence 272
5 Numerical Experiments 273
References 276
Linearly Implicit Domain Decomposition Methods for NonlinearTime-Dependent Reaction-Diffusion Problems 277
1 Introduction 277
2 Spatial Discretization 278
3 Time Integration 279
4 Numerical Results 282
References 284
NKS for Fully Coupled Fluid-Structure Interaction with Application 285
1 Introduction 285
2 Governing Equations 285
3 Spatial Discretization 287
4 Temporal Discretization 288
5 Solving the Nonlinear System 289
6 Numerical Results 290
7 Conclusion 291
References 292
Weak Information Transfer between Non-Matching Warped Interfaces 293
1 Introduction 293
2 Discrete Information Transfer 294
3 The Discrete Coupling Operator 295
4 Numerical Results 299
References 300
Computational Tool for a Mini-Windmill Study with SOFT 301
1 Introduction and Motivation 301
2 Flow Solver 303
3 FSI 304
4 Parallel Computing Scenario and Conclusion 306
References 307
On Preconditioners for Generalized Saddle Point Problemswith an Indefinite Block 308
1 Introduction 308
2 General Assumptions 309
3 Block Diagonal Preconditioner 311
4 Block Upper Triangular Preconditioner 311
5 Lower Block Triangular Preconditioner 312
6 Numerical Experiments 313
7 Conclusions 314
References 314
Lower Bounds for Eigenvalues of Elliptic Operators by OverlappingDomain Decomposition 316
1 Introduction 316
2 Description of the Method 317
3 Two Simple Examples 321
References 322
From the Boundary Element Domain Decomposition Methods to LocalTrefftz Finite Element Methods on Polyhedral Meshes 324
1 Introduction 324
2 The Potential Equation 325
3 The Helmholtz Equation 328
4 The Maxwell Equations 328
5 Conclusions 330
References 330
An Additive Neumann-Neumann Method for Mortar Finite Elementfor 4th Order Problems 332
1 Introduction 332
2 Discrete Problem 333
3 Neumann-Neumann Method 335
3.1 Local Subspaces 335
3.2 Coarse Space 336
References 338
A Numerically Efficient Scheme for Elastic Immersed Boundaries 340
1 Introduction 340
2 Discretization of the IBM 340
3 Volume Conservation Method Based on Constrained Optimization 342
4 Application of the IBM and Conclusion 345
References 346
A Domain Decomposition Method Based on Augmented Lagrangianwith a Penalty Term 348
1 Introduction 348
2 Saddle-Point Formulation 349
3 Iterative Substructuring Method 350
4 Computational Issues and Numerical Results 352
4.1 Computational Issues 352
4.2 Numerical Results 353
5 Conclusions 354
References 355
Parallelization of a Constrained Three-Dimensional Maxwell Solver 356
1 Introduction 356
2 Constrained Wave Equation Formulation 357
3 Variational Formulations 357
4 Space and Time Discretization 359
5 Solution of the Doubly Constrained System 361
6 Numerical Application 362
7 Conclusion 363
References 363
A Discovery Algorithm for the Algebraic Construction of OptimizedSchwarz Preconditioners 364
1 Introduction 364
2 Discovery Algorithm 365
2.1 Interface Detection 366
2.2 Extraction of Physical and Discretization Parameters 366
2.3 Construction of the Optimized Transmission Condition 367
3 Numerical Experiments 369
References 371
On the Convergence of Optimized Schwarz Methodsby way of Matrix Analysis 372
1 Introduction 372
1.1 Model Problem and Notation 373
2 Convergence of OSM 375
3 Numerical Experiments 377
References 378

Produkt-Details

• Erscheint lt. Verlag: 1.9.2009
• Reihe/Serie: Lecture Notes in Computational Science and Engineering
• Reihe/Serie: Lecture Notes in Computational Science and Engineering
• Zusatzinfo: XVI, 376 p. 81 illus.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie
• Themenwelt: Technik
• Schlagworte: algorithms • Approximation • Complexity • domain decomposition • finite elements • Graph • Information • Matching • Optimization • Parallel Computing • preconditioned conjugate gradients
• ISBN-10: 3-642-02677-X / 364202677X
• ISBN-13: 978-3-642-02677-5 / 9783642026775