Multigrid (eBook)

Cornelius W. Oosterlee, Anton Schuller, Ulrich Trottenberg (Autoren)

eBook Download: EPUB

2000 | 1. Auflage
631 Seiten
Elsevier Science (Verlag)
978-0-08-047956-9 (ISBN)

Infos

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

Inhalt

Cover 1
Copyright Page 5
Contents 6
Preface 14
Chapter 1. Introduction 18
1.1 Types of PDEs 18
1.2 Grids and Discretization Approaches 20
1.3 Some Notation 24
1.4 Poisson’s Equation and Model Problem 1 27
1.5 A First Glance at Multigrid 32
1.6 Intermezzo: Some Basic Facts and Methods 41
Chapter 2. Basic Multigrid I 45
2.1 Error Smoothing Procedures 45
2.2 Introducing the Two-grid Cycle 51
2.3 Multigrid Components 58
2.4 The Multigrid Cycle 62
2.5 Multigrid Convergence and Efficiency 69
2.6 Full Multigrid 73
2.7 Further Remarks on Transfer Operators 77
2.8 First Generalizations 79
2.9 Multigrid in 3D 88
Chapter 3. Elementary Multigrid Theory 92
3.1 Survey 93
3.2 Why it is Sufficient to Derive Two-grid Convergence Factors 94
3.3 How to Derive Two-grid Convergence Factors by Rigorous Fourier Analysis 99
3.4 Range of Applicability of the Rigorous Fourier Analysis, Other Approaches 108
Chapter 4. Local Fourier Analysis 115
4.1 Background 116
4.2 Terminology 117
4.3 Smoothing Analysis I 119
4.4 Two-grid Analysis 123
4.5 Smoothing Analysis II 130
4.6 Some Results, Remarks and Extensions 133
4.7 h-Ellipticity 138
Chapter 5. Basic Multigrid II 147
5.1 Anisotropic Equations in 2D 148
5.2 Anisotropic Equations in 3D 158
5.3 Nonlinear Problems, the Full Approximation Scheme 163
5.4 Higher Order Discretizations 183
5.5 Domains with Geometric Singularities 191
5.6 Boundary Conditions and Singular Systems 194
5.7 Finite Volume Discretization and Curvilinear Grids 204
5.8 General Grid Structures 207
Chapter 6. Parallel Multigrid in Practice 210
6.1 Parallelism of Multigrid Components 211
6.2 Grid Partitioning 214
6.3 Grid Partitioning and Multigrid 225
6.4 Parallel Line Smoothers 233
6.5 Modifications of Multigrid and Related Approaches 238
Chapter 7. More Advanced Multigrid 244
7.1 The Convection–Diffusion Equation: Discretization I 245
7.2 The Convection–Diffusion Equation: Multigrid I 251
7.3 The Convection–Diffusion Equation: Discretization II 260
7.4 The Convection–Diffusion Equation: Multigrid II 266
7.5 ILU Smoothing Methods 273
7.6 Problems with Mixed Derivatives 280
7.7 Problems with Jumping Coefficients and Galerkin Coarse Grid Operators 285
7.8 Multigrid as a Preconditioner (Acceleration of Multigrid by Iterant Recombination) 295
Chapter 8. Multigrid for Systems of Equations 306
8.1 Notation and Introductory Remarks 307
8.2 Multigrid Components 310
8.3 LFA for Systems of PDEs 314
8.4 The Biharmonic System 318
8.5 A Linear Shell Problem 324
8.6 Introduction to Incompressible Navier–Stokes Equations 329
8.7 Incompressible Navier–Stokes Equations: Staggered Discretizations 333
8.8 Incompressible Navier–Stokes Equations: Nonstaggered Discretizations 343
8.9 Compressible Euler Equations 360
Chapter 9. Adaptive Multigrid 373
9.1 A Simple Example and Some Notation 374
9.2 The Idea of Adaptive Multigrid 378
9.3 Adaptive Multigrid and the Composite Grid 383
9.4 Refinement Criteria and Optimal Grids 390
9.5 Parallel Adaptive Multigrid 396
9.6 Some Practical Results 399
Chapter 10. Some More Multigrid Applications 406
10.1 Multigrid for Poisson-type Equations on the Surface of the Sphere 406
10.2 Multigrid and Continuation Methods 412
10.3 Generation of Boundary Fitted Grids 417
10.4 LiSS: a Generic Multigrid Software Package 421
10.5 Multigrid in the Aerodynamic Industry 424
10.6 How to Continue with Multigrid 428
Appendixes 430
Appendix A. An Introduction to Algebraic Multigrid (by Klaus Stüben) 430
A.1 Introduction 430
A.2 Theoretical Basis and Notation 439
A.3 Algebraic Smoothing 449
A.4 Postsmoothing and Two-level Convergence 461
A.5 Presmoothing and Two-level Convergence 478
A.6 Limits of the Theory 486
A.7 The Algebraic Multigrid Algorithm 489
A.8 Applications 502
A.9 Aggregation-based Algebraic Multigrid 539
A.10 Further Developments and Conclusions 545
Appendix B. Subspace Correction Methods and Multigrid Theory (by Peter Oswald) 550
B.1 Introduction 550
B.2 Space Splittings 553
B.3 Convergence Theory 568
B.4 Multigrid Applications 573
B.5 A Domain Decomposition Example 578
Appendix C. Recent Developments in Multigrid Efficiency in Computational Fluid Dynamics (by Achi Brandt) 590
C.1 Introduction 590
C.2 Table of Difficulties and Possible Solutions 591
References 607
Index 630

Textauszug

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 aij, ai, ao and a right-hand side f which, in general, may depend on x, y, u, ux, uy (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 = −uxx − uyy = f,

• the wave equation uxx − uyy = 0,

• the heat equation uxx − uy = 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 −εuxx − uyy = f,

• the convection-diffusion equation −εΔu + a1ux + a2uy = f,

• the equation with mixed derivatives −Δu + τuxy = 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 Eh“, 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, except the wave and the heat conduction equations, are typically connected with pure boundary conditions. The wave and the heat conduction equations are typically characterized by initial conditions with respect to one of the variables (y) and by boundary conditions with respect to the other (x).

We will call problems which are characterized by pure boundary conditions space-type problems. For problems with initial conditions, we interpret the variable for which the initial condition is stated as the time variable t (= y), and call these problems time-type. Usually these problems exhibit a marching or evolution behavior with respect to t. Space-type equations, on the other hand, usually describe stationary situations. Note that this distinction is different from the standard classification of elliptic, hyperbolic and parabolic. Elliptic problems are usually space-type while hyperbolic and parabolic problems are often time-type. However, the stationary supersonic full potential equation, the convection equation (see Chapter 7) and the stationary Euler equations (see Section 8.9) are examples of hyperbolic equations with space-type behavior. (In certain situations, the same equation can be interpreted as space- or as time-type, and each interpretation may have its specific meaning. An example is the convection equation.)

In this book, we will present and discuss multigrid methods for space-type problems.

For time-type problems, there is usually the option to discretize the time variable explicitly, implicitly or in a hybrid manner (i.e. semi-implicitly). The implicit or semi-implicit discretization yields discrete space-type problems which have to be solved in each time step. We will briefly consider multigrid approaches for the solution of such space-type problems which arise in each time step in Section 2.8. Typically, these problems have similar but more convenient numerical properties than the corresponding stationary problems with respect to multigrid.

Remark 1.1.1

Some authors have proposed multigrid approaches which include the time direction directly. These approaches consider time to be just another “space-type” direction. Such approaches are discussed in [78, 175, 198, 199, 396] for so-called parabolic multigrid and multigrid-like methods based on “waveform relaxation”.

1.2 GRIDS AND DISCRETIZATION APPROACHES

In this book, we assume that the differential equations to be solved are discretized on a suitable grid (or, synonymously, mesh). Here, we give a rough survey (with some examples) of those types of grids which are treated systematically in this book and those which are only touched on. We also make some remarks about discretization approaches.

1.2.1 Grids

The general remarks in this section may not be so interesting to multigrid beginners. They may start with Section 1.4 on Poisson’s equation and return to this section later.

Most parts of this book refer to: Cartesian grids, boundary-fitted logically rectangular grids and block-structured boundary-fitted grids. Figure 1.1 is an example of a Cartesian grid. For simple domains with simple boundaries, Cartesian grids are numerically convenient. We will use them for Model Problem 1 (see Section 1.3.2) and several other cases.

Figure 1.1 A square Cartesian grid (left) in a domain Ω and a boundary-fitted curvilinear (logically rectangular) grid (right).

Figure 1.1 also gives an example of a boundary-fitted grid. Boundary-fitted grids will be used in more advanced examples in this book. A systematic introduction into boundary-fitted grids is given in [391]. We will discuss the generation of boundary-fitted grids in Section 10.3.

In the context of boundary-fitted grids, there are two different approaches. In the first, coordinate transformations are used to obtain simple (for example rectangular) domains, and correspondingly simple (rectangular) grids. Here the differential (and/or the discrete) equations are transformed to the new curvilinear coordinates. In the second approach, the computations are performed in the physical domain with the original (nontransformed) equations. In this book we concentrate on the second approach.

Block-structured boundary-fitted grids are used if the given domain cannot (or cannot reasonably) be mapped to a rectangular domain, but can be decomposed into a finite number of subdomains each of which can be covered with a boundary-fitted grid. Quite complicated domains may be treated with this approach, as can be seen in Fig. 1.2. Block-structured boundary-fitted grids are discussed in Chapters 6 and chapter 8–10.

Figure 1.2 Boundary-fitted block-structured grid around a car.

In many software packages, unstructured, irregular grids are used today. These grids have become quite popular because unstructured automatic mesh generation is...

Produkt-Details

• Erscheint lt. Verlag: 20.11.2000
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie
• Themenwelt: Technik
• ISBN-10: 0-08-047956-1 / 0080479561
• ISBN-13: 978-0-08-047956-9 / 9780080479569