多重网格 英文PDF电子书下载

1 Introduction 1

1.1 Types of PDEs 1

1.2 Grids and Discretization Approaches 3

1.2.1 Grids 3

1.2.2 Discretization Approaches 6

1.3 SomeNotation 7

1.3.1 Continuous Boundary Value Problems 8

1.3.2 Discrete Boundary Value Problems 8

1.3.3 Inner Products and Norms 9

1.3.4 Stencil Notation 10

1.4 Poisson's Equation and Model Problem 1 10

1.4.1 Matrix Terminology 12

1.4.2 Poisson Solvers 14

1.5 A First Glance at Multigrid 15

1.5.1 The Two Ingredients of Multigrid 15

1.5.2 High and Low Frequencies,and Coarse Meshes 17

1.5.3 From Two Grids to Multigrid 19

1.5.4 Multigrid Features 20

1.5.5 Multigrid History 23

1.6 Intermezzo:Some Basic Facts and Methods 24

1.6.1 Iterative Solvers,Splittings and Preconditioners 24

2 Basic Multigrid I 28

2.1 Error Smoothing Procedures 28

2.1.1 Jacobi-type Iteration(Relaxation) 29

2.1.2 Smoothing Properties of ω-Jacobi Relaxation 30

2.1.3 Gauss-Seidel-type Iteration(Relaxation) 31

2.1.4 Parallel Properties of Smoothers 33

2.2 Introducing the Two-grid Cycle 34

2.2.1 Iteration by Approximate Solution of the Defect Equation 35

2.2.2 Coarse Grid Correction 37

2.2.3 Structure of the Two-grid Operator 39

2.3 Multigrid Components 41

2.3.1 Choices of Coarse Grids 41

2.3.2 Choice of the Coarse Grid Operator 42

2.3.3 Transfer Operators:Restriction 42

2.3.4 Transfer Operators:Interpolation 43

2.4 The Multigrid Cycle 45

2.4.1 Sequences of Grids and Operators 46

2.4.2 Recursive Definition 46

2.4.3 Computational Work 50

2.5 Multigrid Convergence and Efficiency 52

2.5.1 An Efficient 2D Multigrid Poisson Solver 52

2.5.2 How to Measure the Multigrid Convergence Factor in Practice 54

2.5.3 Numerical Efficiency 55

2.6 Full Multigrid 56

2.6.1 Structure of Full Multigrid 57

2.6.2 Computational Work 59

2.6.3 FMG for Poisson's Equation 59

2.7 Further Remarks on Transfer Operators 60

2.8 First Generalizations 62

2.8.1 2D Poisson-like Differential Equations 62

2.8.2 Time-dependent Problems 63

2.8.3 Cartesian Grids in Nonrectangular Domains 66

2.8.4 Multigrid Components for Cell-centered Discretizations 69

2.9 Multigrid in 3D 70

2.9.1 The 3D Poisson Problem 70

2.9.2 3D Multigrid Components 71

2.9.3 Computational Work in 3D 74

3 Elementary Multigrid Theory 75

3.1 Survey 76

3.2 Why it is Sufficient to Derive Two-grid Convergence Factors 77

3.2.1 h-Independent Convergence of Multigrid 77

3.2.2 A Theoretical Estimate for Full Multigrid 79

3.3 How to Derive Two-grid Convergence Factors by Rigorous Fourier Analysis 82

3.3.1 Asymptotic Two-grid Convergence 82

3.3.2 Norms of the Two-grid Operator 83

3.3.3 Results for Multigrid 85

3.3.4 Essential Steps and Details of the Two-grid Analysis 85

3.4 Range of Applicability of the Rigorous Fourier Analysis,Other Approaches 91

3.4.1 The 3D Case 91

3.4.2 Boundary Conditions 93

3.4.3 List of Applications and Limitations 93

3.4.4 Towards Local Fourier Analysis 94

3.4.5 Smoothing and Approximation Property:a Theoretical Overview 96

4 Local Fourier Analysis 98

4.1 Background 99

4.2 Terminology 100

4.3 Smoothing Analysis Ⅰ 102

4.4 Two-grid Analysis 106

4.5 Smoothing Analysis Ⅱ 113

4.5.1 Local Fourier Analysis for GS-RB 115

4.6 Some Results,Remarks and Extensions 116

4.6.1 Some Local Fourier Analysis Results for Model Problem 1 117

4.6.2 Additional Remarks 118

4.6.3 Other Coarsening Strategies 121

4.7 h-Ellipticity 121

4.7.1 The Concept of h-Ellipticity 123

4.7.2 Smoothing and h-Ellipticity 126

5 Basic Multigrid Ⅱ 130

5.1 Anisotropic Equations in 2D 131

5.1.1 Failure of Pointwise Relaxation and Standard Coarsening 131

5.1.2 Semicoarsening 133

5.1.3 Line Smoothers 134

5.1.4 Strong Coupling of Unknowns in Two Directions 137

5.1.5 An Example with Varying Coefficients 139

5.2 Anisotropic Equations in 3D 141

5.2.1 Standard Coarsening for 3D Anisotropic Problems 143

5.2.2 Point Relaxation for 3D Anisotropic Problems 145

5.2.3 Further Approaches,Robust Variants 147

5.3 Nonlinear Problems,the Full Approximation Scheme 147

5.3.1 Classical Numerical Methods for Nonlinear PDEs:an Example 148

5.3.2 Local Linearization 151

5.3.3 Linear Multigrid in Connection with Global Linearization 153

5.3.4 Nonlinear Multigrid:the Full Approximation Scheme 155

5.3.5 Smoothing Analysis:a Simple Example 159

5.3.6 FAS for the Full Potential Equation 160

5.3.7 The(h,H)-Relative Truncation Error and τ-Extrapolation 163

5.4 Higher Order Discretizations 166

5.4.1 Defect Correction 168

5.4.2 The Mehrstellen Discretization for Poisson's Equation 172

5.5 Domains with Geometric Singularities 174

5.6 Boundary Conditions and Singular Systems 177

5.6.1 General Treatment of Boundary Conditions in Multigrid 178

5.6.2 Neumann Boundary Conditions 179

5.6.3 Periodic Boundary Conditions and Global Constraints 183

5.6.4 General Treatment of Singular Systems 185

5.7 Finite Volume Discretization and Curvilinear Grids 187

5.8 General Grid Structures 190

6 Parallel Multigrid in Practice 193

6.1 Parallelism of Multigrid Components 194

6.1.1 Parallel Components for Poisson's Equation 195

6.1.2 Parallel Complexity 196

6.2 Grid Partitioning 197

6.2.1 Parallel Systems,Processes and Basic Rules for Parallelization 198

6.2.2 Grid Partitioning for Jacobi and Red-Black Relaxation 199

6.2.3 Speed-up and Parallel Efficiency 204

6.2.4 A Simple Communication Model 206

6.2.5 Scalability and the Boundary-volume Effect 207

6.3 Grid Partitioning and Multigrid 208

6.3.1 Two-grid and Basic Multigrid Considerations 208

6.3.2 Multigrid and the Verv Coarse Grids 211

6.3.3 Boundary-volume Effect and Scalability in the Multigrid Context 214

6.3.4 Programming Parallel Systems 215

6.4 Parallel Line Smoothers 216

6.4.1 1D Reduction(or Cyclic Reduction)Methods 217

6.4.2 Cyclic Reduction and Grid Partitioning 218

6.4.3 Parallel Plane Relaxation 220

6.5 Modifications of Multigrid and Related Approaches 221

6.5.1 Domain Decomposition Methods:a Brief Survey 221

6.5.2 Multigrid Related Parallel Approaches 225

7 More Advanced Multigrid 227

7.1 The Convection-Diffusion Equation:Discretization Ⅰ 228

7.1.1 The 1D Case 228

7.1.2 Central Differencing 230

7.1.3 First-order Upwind Discretizations and Artificial Viscosity 233

7.2 The Convection-Diffusion Equation:Multigrid Ⅰ 234

7.2.1 Smoothers for First-order Upwind Discretizations 235

7.2.2 Variable Coefficients 237

7.2.3 The Coarse Grid Correction 239

7.3 The Convection-Diffusion Equation:Discretization Ⅱ 243

7.3.1 Combining Central and Upwind Differencing 243

7.3.2 Higher Order Upwind Discretizations 244

7.4 The Convection-Diffusion Equation:Multigrid Ⅱ 249

7.4.1 Line Smoothers for Higher Order Upwind Discretizations 249

7.4.2 Multistage Smoothers 253

7.5 ILU Smoothing Methods 256

7.5.1 Idea of ILU Smoothing 257

7.5.2 Stencil Noration 259

7.5.3 ILU Smoothing for the Anisotropic Diffusion Equation 261

7.5.4 A Particularly Robust ILU Smoother 262

7.6 Problems with Mixed Derivatives 263

7.6.1 Standard Smoothing and Coarse Grid Correction 264

7.6.2 ILU Smoothing 267

7.7 Problems with Jumping Coefficients and Galerkin Coarse Grid Operators 268

7.7.1 Jumping Coefficients 269

7.7.2 Multigrid for Problems with Jumping Coefficients 271

7.7.3 Operator-dependent Interpolation 272

7.7.4 The Galerkin Coarse Grid Operator 273

7.7.5 Further Remarks on Galerkin-based Coarsening 277

7.8 Multigrid as a Preconditioner(Acceleration of Multigrid by Iterant Recombination) 278

7.8.1 The Recirculating Convection-Diffusion Problem Revisited 278

7.8.2 Multigrid Acceleration by Iterant Recombination 280

7.8.3 Krylov Subspace Iteration and Multigrid Preconditioning 282

7.8.4 Multigrid:Solver versus Preconditioner 287

8 Multigrid for Systems of Equations 289

8.1 Notation and Introductory Remarks 290

8.2 Multigrid Components 293

8.2.1 Restriction 293

8.2.2 Interpolation of Coarse Grid Corrections 294

8.2.3 Orders of Restriction and Interpolation 295

8.2.4 Solution on the Coarsest Grid 295

8.2.5 Smoothers 295

8.2.6 Treatment of Boundary Conditions 296

8.3 LFA for Systems of PDEs 297

8.3.1 Smoothing Analysis 297

8.3.2 Smoothing and h-Ellipticity 300

8.4 The Biharmonic System 301

8.4.1 A Simple Example:GS-LEX Smoothing 302

8.4.2 Treatment of Boundary Conditions 303

8.4.3 Multigrid Convergence 304

8.5 A Linear Shell Problem 307

8.5.1 Decoupled Smoothing 308

8.5.2 Collective versus Decoupled Smoothing 310

8.5.3 Level-dependent Smoothing 311

8.6 Introduction to Incompressible Navier-Stokes Equations 312

8.6.1 Equations and Boundary Conditions 312

8.6.2 Survey 314

8.6.3 The Checkerboard Instability 315

8.7 Incompressible Navier-Stokes Equations:Staggered Discretizations 316

8.7.1 Transfer Operators 318

8.7.2 Box Smoothing 320

8.7.3 Distributive Smoothing 323

8.8 Incompressible Navier-Stokes Equations:Nonstaggered Discretizations 326

8.8.1 Artificial Pressure Terms 327

8.8.2 Box Smoothing 328

8.8.3 Alternative Formulations 331

8.8.4 Flux Splitting Concepts 333

8.8.5 Flux Difference Splitting and Multigrid:Examples 338

8.9 Compressible Euler Equations 343

8.9.1 Introduction 345

8.9.2 Finite Volume Discretization and Appropriate Smoothers 347

8.9.3 Some Examples 349

8.9.4 Multistage Smoothers in CFD Applications 352

8.9.5 Towards Compressible Navier-Stokes Equations 354

9 Adaptive Multigrid 356

9.1 A Simple Example and Some Notation 357

9.1.1 A Simple Example 357

9.1.2 Hierarchy of Grids 360

9.2 The Idea of Adaptive Multigrid 361

9.2.1 The Two-grid Case 361

9.2.2 From Two Grids to Multigrid 363

9.2.3 Self-adaptive Full Multigrid 364

9.3 Adaptive Multigrid and the Composite Grid 366

9.3.1 Conservative Discretization at Interfaces of Refinement Areas 367

9.3.2 Conservative Interpolation 369

9.3.3 The Adaptive Multigrid Cycle 372

9.3.4 Further Approaches 373

9.4 Refinement Criteria and Optimal Grids 373

9.4.1 Refinement Criteria 374

9.4.2 Optimal Grids and Computational Effort 378

9.5 Parallel Adaptive Multigrid 379

9.5.1 Parallelization Aspects 379

9.5.2 Distribution of Locally Refined Grids 381

9.6 Some Practical Results 382

9.6.1 2D Euler Flow Around an Airfoil 382

9.6.2 2D and 3D Incompressible Navier-Stokes Equations 385

10 Some More Multigrid Applications 389

10.1 Multigrid for Poisson-type Equations on the Surface of the Sphere 389

10.1.1 Discretization 390

10.1.2 Specific Multigrid Components on the Surface of a Sphere 391

10.1.3 A Segment Relaxation 393

10.2 Multigrid and Continuation Methods 395

10.2.1 The Bratu Problem 396

10.2.2 Continuation Techniques 397

10.2.3 Multigrid for Continuation Methods 398

10.2.4 The Indefinite Helmholtz Equation 400

10.3 Generation of Boundary Fitted Grids 400

10.3.1 Grid Generation Based on Poisson's Equation 401

10.3.2 Multigrid Solution of Grid Generation Equations 401

10.3.3 Grid Generation with the Biharmonic Equation 403

10.3.4 Examples 404

10.4 LiSS:a Generic Multigrid Software Package 404

10.4.1 Pre-and Postprocessing Components 405

10.4.2 The Multigrid Solver 406

10.5 Multigrid in the Aerodynamic Industry 407

10.5.1 Numerical Challenges for the 3D Compressible Navier-Stokes Equations 408

10.5.2 FLOWer 409

10.5.3 Fluid-Structure Coupling 410

10.6 How to Continue with Multigrid 411

Appendixes 413

A An Introduction to Algebraic Multigrid(by Klaus Stüben) 413

A.1 Introduction 413

A.1.1 Geometric Multigrid 414

A.1.2 Algebraic Multigrid 415

A.1.3 An Example 418

A.1.4 Overview of the Appendix 420

A.2 Theoretical Basis and Notation 422

A.2.1 Formal Algebraic Multigrid Components 422

A.2.2 Further Notation 425

A.2.3 Limit Case of Direct Solvers 427

A.2.4 The Variational Principle for Positive Definite Problems 430

A.3 Algebraic Smoothing 432

A.3.1 Basic Norms and Smooth Eigenvectors 433

A.3.2 Smoothing Property of Relaxation 434

A.3.3 Interpretation of Algebraically Smooth Error 438

A.4 Postsmoothing and Two-level Convergence 444

A.4.1 Convergence Estimate 445

A.4.2 Direct Interpolation 447

A.4.3 Indirect Interpolation 459

A.5 Presmoothing and Two-level Convergence 461

A.5.1 Convergence using Mere F-Smoothing 461

A.5.2 Convergence using Full Smoothing 468

A.6 Limits of the Theory 469

A.7 The Algebraic Multigrid Algorithm 472

A.7.1 Coarsening 473

A.7.2 Interpolation 479

A.7.3 Algebraic Multigrid as Preconditioner 484

A.8 Applications 485

A.8.1 Default Settings and Notation 486

A.8.2 Poisson-like Problems 487

A.8.3 Computational Fluid Dynamics 494

A.8.4 Problems with Discontinuous Coefficients 503

A.8.5 Further Model Problems 513

A.9 Aggregation-based Algebraic Multigrid 522

A.9.1 Rescaling of the Galerkin Operator 524

A.9.2 Smoothed Aggregation 526

A.10 Further Developments and Conclusions 528

B Subspace Correction Methods and Multigrid Theory(by Peter Oswald) 533

B.1 Introduction 533

B.2 Space Splittings 536

B.3 Convergence Theory 551

B.4 Multigrid Applications 556

B.5 A Domain Decomposition Example 561

C Recent Developments in Multigrid Efficiency in Computational Fluid Dynamics(by Achi Brandt) 573

C.1 Introduction 573

C.2 Table of Difficulties and Possible Solutions 574

References 590

Index 613