1 Introduction

1.1 Types of PDEs

1.2 Grids and Discretization Approaches

1.2.1 Grids

1.2.2 Discretization Approaches

1.3 SomeNotation

1.3.1 Continuous Boundary Value Problems

1.3.2 Discrete Boundary Value Problems

1.3.3 Inner Products and Norms

1.3.4 Stencil Notation

1.4 Poisson's Equation and Model Problem 1

1.4.1 Matrix Terminology

1.4.2 Poisson Solvers

1.5 A First Glance at Multigrid

1.5.1 The Two Ingredients of Multigrid

1.5.2 High and Low Frequencies,and Coarse Meshes

1.5.3 From Two Grids to Multigrid

1.5.4 Multigrid Features

1.5.5 Multigrid History

1.6 Intermezzo:Some Basic Facts and Methods

1.6.1 Iterative Solvers,Splittings and Preconditioners

2 Basic Multigrid I

2.1 Error Smoothing Procedures

2.1.1 Jacobi-type Iteration(Relaxation)

2.1.2 Smoothing Properties of ω-Jacobi Relaxation

2.1.3 Gauss-Seidel-type Iteration(Relaxation)

2.1.4 Parallel Properties of Smoothers

2.2 Introducing the Two-grid Cycle

2.2.1 Iteration by Approximate Solution of the Defect Equation

2.2.2 Coarse Grid Correction

2.2.3 Structure of the Two-grid Operator

2.3 Multigrid Components

2.3.1 Choices of Coarse Grids

2.3.2 Choice of the Coarse Grid Operator

2.3.3 Transfer Operators:Restriction

2.3.4 Transfer Operators:Interpolation

2.4 The Multigrid Cycle

2.4.1 Sequences of Grids and Operators

2.4.2 Recursive Definition

2.4.3 Computational Work

2.5 Multigrid Convergence and Efficiency

2.5.1 An Efficient 2D Multigrid Poisson Solver

2.5.2 How to Measure the Multigrid Convergence Factor in Practice

2.5.3 Numerical Efficiency

2.6 Full Multigrid

2.6.1 Structure of Full Multigrid

2.6.2 Computational Work

2.6.3 FMG for Poisson's Equation

2.7 Further Remarks on Transfer Operators

2.8 First Generalizations

2.8.1 2D Poisson-like Differential Equations

2.8.2 Time-dependent Problems

2.8.3 Cartesian Grids in Nonrectangular Domains

2.8.4 Multigrid Components for Cell-centered Discretizations

2.9 Multigrid in 3D

2.9.1 The 3D Poisson Problem

2.9.2 3D Multigrid Components

2.9.3 Computational Work in 3D

3 Elementary Multigrid Theory

3.1 Survey

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

3.2.1 h-Independent Convergence of Multigrid

3.2.2 A Theoretical Estimate for Full Multigrid

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

3.3.1 Asymptotic Two-grid Convergence

3.3.2 Norms of the Two-grid Operator

3.3.3 Results for Multigrid

3.3.4 Essential Steps and Details of the Two-grid Analysis

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

3.4.1 The 3D Case

3.4.2 Boundary Conditions

3.4.3 List of Applications and Limitations

3.4.4 Towards Local Fourier Analysis

3.4.5 Smoothing and Approximation Property:a Theoretical Overview

4 Local Fourier Analysis

4.1 Background

4.2 Terminology

4.3 Smoothing Analysis Ⅰ

4.4 Two-grid Analysis

4.5 Smoothing Analysis Ⅱ

4.5.1 Local Fourier Analysis for GS-RB

4.6 Some Results,Remarks and Extensions

4.6.1 Some Local Fourier Analysis Results for Model Problem 1

4.6.2 Additional Remarks

4.6.3 Other Coarsening Strategies

4.7 h-Ellipticity

4.7.1 The Concept of h-Ellipticity

4.7.2 Smoothing and h-Ellipticity

5 Basic Multigrid Ⅱ

5.1 Anisotropic Equations in 2D

5.1.1 Failure of Pointwise Relaxation and Standard Coarsening

5.1.2 Semicoarsening

5.1.3 Line Smoothers

5.1.4 Strong Coupling of Unknowns in Two Directions

5.1.5 An Example with Varying Coefficients

5.2 Anisotropic Equations in 3D

5.2.1 Standard Coarsening for 3D Anisotropic Problems

5.2.2 Point Relaxation for 3D Anisotropic Problems

5.2.3 Further Approaches,Robust Variants

5.3 Nonlinear Problems,the Full Approximation Scheme

5.3.1 Classical Numerical Methods for Nonlinear PDEs:an Example

5.3.2 Local Linearization

5.3.3 Linear Multigrid in Connection with Global Linearization

5.3.4 Nonlinear Multigrid:the Full Approximation Scheme

5.3.5 Smoothing Analysis:a Simple Example

5.3.6 FAS for the Full Potential Equation

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

5.4 Higher Order Discretizations

5.4.1 Defect Correction

5.4.2 The Mehrstellen Discretization for Poisson's Equation

5.5 Domains with Geometric Singularities

5.6 Boundary Conditions and Singular Systems

5.6.1 General Treatment of Boundary Conditions in Multigrid

5.6.2 Neumann Boundary Conditions

5.6.3 Periodic Boundary Conditions and Global Constraints

5.6.4 General Treatment of Singular Systems

5.7 Finite Volume Discretization and Curvilinear Grids

5.8 General Grid Structures

6 Parallel Multigrid in Practice

6.1 Parallelism of Multigrid Components

6.1.1 Parallel Components for Poisson's Equation

6.1.2 Parallel Complexity

6.2 Grid Partitioning

6.2.1 Parallel Systems,Processes and Basic Rules for Parallelization

6.2.2 Grid Partitioning for Jacobi and Red-Black Relaxation

6.2.3 Speed-up and Parallel Efficiency

6.2.4 A Simple Communication Model

6.2.5 Scalability and the Boundary-volume Effect

6.3 Grid Partitioning and Multigrid

6.3.1 Two-grid and Basic Multigrid Considerations

6.3.2 Multigrid and the Verv Coarse Grids

6.3.3 Boundary-volume Effect and Scalability in the Multigrid Context

6.3.4 Programming Parallel Systems

6.4 Parallel Line Smoothers

6.4.1 1D Reduction(or Cyclic Reduction)Methods

6.4.2 Cyclic Reduction and Grid Partitioning

6.4.3 Parallel Plane Relaxation

6.5 Modifications of Multigrid and Related Approaches

6.5.1 Domain Decomposition Methods:a Brief Survey

6.5.2 Multigrid Related Parallel Approaches

7 More Advanced Multigrid

7.1 The Convection-Diffusion Equation:Discretization Ⅰ

7.1.1 The 1D Case

7.1.2 Central Differencing

7.1.3 First-order Upwind Discretizations and Artificial Viscosity

7.2 The Convection-Diffusion Equation:Multigrid Ⅰ

7.2.1 Smoothers for First-order Upwind Discretizations

7.2.2 Variable Coefficients

7.2.3 The Coarse Grid Correction

7.3 The Convection-Diffusion Equation:Discretization Ⅱ

7.3.1 Combining Central and Upwind Differencing

7.3.2 Higher Order Upwind Discretizations

7.4 The Convection-Diffusion Equation:Multigrid Ⅱ

7.4.1 Line Smoothers for Higher Order Upwind Discretizations

7.4.2 Multistage Smoothers

7.5 ILU Smoothing Methods

7.5.1 Idea of ILU Smoothing

7.5.2 Stencil Noration

7.5.3 ILU Smoothing for the Anisotropic Diffusion Equation

7.5.4 A Particularly Robust ILU Smoother

7.6 Problems with Mixed Derivatives

7.6.1 Standard Smoothing and Coarse Grid Correction

7.6.2 ILU Smoothing

7.7 Problems with Jumping Coefficients and Galerkin Coarse Grid Operators

7.7.1 Jumping Coefficients

7.7.2 Multigrid for Problems with Jumping Coefficients

7.7.3 Operator-dependent Interpolation

7.7.4 The Galerkin Coarse Grid Operator

7.7.5 Further Remarks on Galerkin-based Coarsening

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

7.8.1 The Recirculating Convection-Diffusion Problem Revisited

7.8.2 Multigrid Acceleration by Iterant Recombination

7.8.3 Krylov Subspace Iteration and Multigrid Preconditioning

7.8.4 Multigrid:Solver versus Preconditioner

8 Multigrid for Systems of Equations

8.1 Notation and Introductory Remarks

8.2 Multigrid Components

8.2.1 Restriction

8.2.2 Interpolation of Coarse Grid Corrections

8.2.3 Orders of Restriction and Interpolation

8.2.4 Solution on the Coarsest Grid

8.2.5 Smoothers

8.2.6 Treatment of Boundary Conditions

8.3 LFA for Systems of PDEs

8.3.1 Smoothing Analysis

8.3.2 Smoothing and h-Ellipticity

8.4 The Biharmonic System

8.4.1 A Simple Example:GS-LEX Smoothing

8.4.2 Treatment of Boundary Conditions

8.4.3 Multigrid Convergence

8.5 A Linear Shell Problem

8.5.1 Decoupled Smoothing

8.5.2 Collective versus Decoupled Smoothing

8.5.3 Level-dependent Smoothing

8.6 Introduction to Incompressible Navier-Stokes Equations

8.6.1 Equations and Boundary Conditions

8.6.2 Survey

8.6.3 The Checkerboard Instability

8.7 Incompressible Navier-Stokes Equations:Staggered Discretizations

8.7.1 Transfer Operators

8.7.2 Box Smoothing

8.7.3 Distributive Smoothing

8.8 Incompressible Navier-Stokes Equations:Nonstaggered Discretizations

8.8.1 Artificial Pressure Terms

8.8.2 Box Smoothing

8.8.3 Alternative Formulations

8.8.4 Flux Splitting Concepts

8.8.5 Flux Difference Splitting and Multigrid:Examples

8.9 Compressible Euler Equations

8.9.1 Introduction

8.9.2 Finite Volume Discretization and Appropriate Smoothers

8.9.3 Some Examples

8.9.4 Multistage Smoothers in CFD Applications

8.9.5 Towards Compressible Navier-Stokes Equations

9 Adaptive Multigrid

9.1 A Simple Example and Some Notation

9.1.1 A Simple Example

9.1.2 Hierarchy of Grids

9.2 The Idea of Adaptive Multigrid

9.2.1 The Two-grid Case

9.2.2 From Two Grids to Multigrid

9.2.3 Self-adaptive Full Multigrid

9.3 Adaptive Multigrid and the Composite Grid

9.3.1 Conservative Discretization at Interfaces of Refinement Areas

9.3.2 Conservative Interpolation

9.3.3 The Adaptive Multigrid Cycle

9.3.4 Further Approaches

9.4 Refinement Criteria and Optimal Grids

9.4.1 Refinement Criteria

9.4.2 Optimal Grids and Computational Effort

9.5 Parallel Adaptive Multigrid

9.5.1 Parallelization Aspects

9.5.2 Distribution of Locally Refined Grids

9.6 Some Practical Results

9.6.1 2D Euler Flow Around an Airfoil

9.6.2 2D and 3D Incompressible Navier-Stokes Equations

10 Some More Multigrid Applications

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

10.1.1 Discretization

10.1.2 Specific Multigrid Components on the Surface of a Sphere

10.1.3 A Segment Relaxation

10.2 Multigrid and Continuation Methods

10.2.1 The Bratu Problem

10.2.2 Continuation Techniques

10.2.3 Multigrid for Continuation Methods

10.2.4 The Indefinite Helmholtz Equation

10.3 Generation of Boundary Fitted Grids

10.3.1 Grid Generation Based on Poisson's Equation

10.3.2 Multigrid Solution of Grid Generation Equations

10.3.3 Grid Generation with the Biharmonic Equation

10.3.4 Examples

10.4 LiSS:a Generic Multigrid Software Package

10.4.1 Pre-and Postprocessing Components

10.4.2 The Multigrid Solver

10.5 Multigrid in the Aerodynamic Industry

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

10.5.2 FLOWer

10.5.3 Fluid-Structure Coupling

10.6 How to Continue with Multigrid

Appendixes

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

A.1 Introduction

A.1.1 Geometric Multigrid

A.1.2 Algebraic Multigrid

A.1.3 An Example

A.1.4 Overview of the Appendix

A.2 Theoretical Basis and Notation

A.2.1 Formal Algebraic Multigrid Components

A.2.2 Further Notation

A.2.3 Limit Case of Direct Solvers

A.2.4 The Variational Principle for Positive Definite Problems

A.3 Algebraic Smoothing

A.3.1 Basic Norms and Smooth Eigenvectors

A.3.2 Smoothing Property of Relaxation

A.3.3 Interpretation of Algebraically Smooth Error

A.4 Postsmoothing and Two-level Convergence

A.4.1 Convergence Estimate

A.4.2 Direct Interpolation

A.4.3 Indirect Interpolation

A.5 Presmoothing and Two-level Convergence

A.5.1 Convergence using Mere F-Smoothing

A.5.2 Convergence using Full Smoothing

A.6 Limits of the Theory

A.7 The Algebraic Multigrid Algorithm

A.7.1 Coarsening

A.7.2 Interpolation

A.7.3 Algebraic Multigrid as Preconditioner

A.8 Applications

A.8.1 Default Settings and Notation

A.8.2 Poisson-like Problems

A.8.3 Computational Fluid Dynamics

A.8.4 Problems with Discontinuous Coefficients

A.8.5 Further Model Problems

A.9 Aggregation-based Algebraic Multigrid

A.9.1 Rescaling of the Galerkin Operator

A.9.2 Smoothed Aggregation

A.10 Further Developments and Conclusions

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

B.1 Introduction

B.2 Space Splittings

B.3 Convergence Theory

B.4 Multigrid Applications

B.5 A Domain Decomposition Example

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

C.1 Introduction

C.2 Table of Difficulties and Possible Solutions

References

Index