Multigrid

Ulrich Trottenberg, Cornelius W. Oosterlee, Anton Schuller

• Publisher: Academic Press
• Year: 2000
• Print ISBN: 9780127010700
• eBook ISBN: 9780080479569
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

Multigrid presents both an elementary introduction to multigrid methods for solving partial differential equations and a contemporary survey of advanced multigrid techniques and real-life applications.Multigrid methods are invaluable to researchers in scientific disciplines including physics, chemistry, meteorology, fluid and continuum mechanics, geology, biology, and all engineering disciplines. They are also becoming increasingly important in economics and financial mathematics.Readers are presented with an invaluable summary covering 25 years of practical experience acquired by the multigrid research group at the Germany National Research Center for Information Technology. The book presents both practical and theoretical points of view.* Covers the whole field of multigrid methods from its elements up to the most advanced applications* Style is essentially elementary but mathematically rigorous* No other book is so comprehensive and written for both practitioners and students

1 INTRODUCTION

We start this chapter with a short introduction of some of the equations that we will treat in this book in Section 1.1 and with some information on grids and discretization approaches in Section 1.2. In Section 1.3 we will introduce some of our terminology. The 2D Poisson equation with Dirichlet boundary conditions is the prototype of an elliptic boundary value problem. It is introduced and discussed in Section 1.4. In Section 1.5 we will take a first glance at multigrid and obtain an impression of the multigrid idea. Some facts and methods on basic numerics are listed in Section 1.6.

1.1 TYPES OF PDEs

As we will see in this book, elliptic boundary value problems are the type of problem to which multigrid methods can be applied very efficiently. However, multigrid or multigrid-like methods have also been developed for many PDEs with nonelliptic features.

We will start with the usual classification of second-order scalar 2D PDEs. Generalizations of this classification to 3D, higher order equations or systems of PDEs can be found [150]. We consider equations Lu = f in some domain

where

(1.1.1)

with coefficients a_ij, a_i, a_o and a right-hand side f which, in general, may depend on x, y, u, u_x, u_y (the quasilinear case). In most parts of this book, Lu = f is assumed to be a linear differential equation, which means that the coefficients and the right-hand side f only depend on (x, y). L is called

• elliptic if

• hyperbolic if

• parabolic if

.

In general, this classification depends on (x, y) and, in the nonlinear case, also on the solution u. Prototypes of the above equation are

• the Poisson equation −Δu = −u_xx − u_yy = f,

• the wave equation u_xx − u_yy = 0,

• the heat equation u_xx − u_y = 0.

Since multigrid methods work excellently for nicely elliptic problems, most of our presentation in the first chapters is oriented to Poisson’s and Poisson-like equations. Other important model equations that we will treat in this book include

• the anisotropic model equation −εu_xx − u_yy = f,

• the convection-diffusion equation −εΔu + a₁u_x + a₂u_y = f,

• the equation with mixed derivatives −Δu + τu_xy = f.

All these equations will serve as model equations for special features and complications and are thus representative of a larger class of problems with similar features. These model equations depend crucially on a parameter ε or τ. For certain parameter values we have a singular perturbation: the type of the equation changes and the solution behaves qualitatively different (if it exists at all). For instance, the anisotropic equation becomes parabolic for ε → 0, the equation with mixed derivatives is elliptic for |τ| < 2, parabolic for |τ| = 2 and hyperbolic for |τ| > 2. All the model equations represent classes of problems which are of practical relevance.

In this book, the applicability of multigrid is connected to a quantity, the “h-ellipticity measure E_h“, that we will introduce in Section 4.7. This h-ellipticity measure is not applied to the differential operator itself, but to the corresponding discrete operator. It can be used to analyze whether or not the discretization is appropriate for a straightforward multigrid treatment. Nonelliptic problems can also have some h-ellipticity if discretized accordingly.

The above model equations, excep...

Table of contents

• Cover image
• Title page
• Table of Contents
• Dedication
• Copyright
• PREFACE
• Chapter 1: INTRODUCTION
• Chapter 2: BASIC MULTIGRID I
• Chapter 3: ELEMENTARY MULTIGRID THEORY
• Chapter 4: LOCAL FOURIER ANALYSIS
• Chapter 5: BASIC MULTIGRID II
• Chapter 6: PARALLEL MULTIGRID IN PRACTICE
• Chapter 7: MORE ADVANCED MULTIGRID
• Chapter 8: MULTIGRID FOR SYSTEMS OF EQUATIONS
• Chapter 9: ADAPTIVE MULTIGRID
• Chapter 10: SOME MORE MULTIGRID APPLICATIONS
• Appendixes
• REFERENCES
• INDEX