Multi-Grid Methods and Applications

Frontmatter

1. Preliminaries

Abstract

The numerical solution of boundary value problems is indispensable in almost all fields of physics and engineering sciences. The recent development, e.g. the study of three-dimensional problems, leads to systems of a larger and larger number of equations. Although the computers have become faster and vector computers are available, new numerical methods are required. A step in this direction was the development of fast Poisson solvers in the late sixties. At that time it seemed that there exist faster numerical methods the simpler the discrete elliptic problem. The first multi-grid methods have also been applied to Poisson's equation and show an efficiency similar to that of the direct solvers. But differently from other numerical methods, the efficiency is not lost when more involved problems are to be solved.

Wolfgang Hackbusch

2. Introductory Model Problem

Abstract

A natural model of an elliptic equation is the two-dimensional Poisson equation in a square. Unfortunately, the analysis of the multi-grid algorithm for this problem is still an involved exercise. Therefore, we start with the simplest one-dimensional Dirichlet boundary value problem

$$ - u''\left( x \right) = f\left( x \right)in\Omega = \left( {0,1} \right)u\left( x \right) = 0atx \in \Gamma = \left\{ {0,1} \right\}$$

(2.1.1)

.

Wolfgang Hackbusch

3. General Two-Grid Method

Abstract

The complete multi-grid process will be developed in three stages (§ 3: two-grid iteration, § 4: multi-grid iteration, § 5: nested iteration). The two-grid algorithm serves only as an (impractical) illustration preparing for the multi-grid method which might seem intricate if introduced at once. Although the multi-grid iteration of § 4 is already effective, it can still be improved by the nested iteration (§ 5).

Wolfgang Hackbusch

4. General Multi-Grid Iteration

Abstract

The extension of the two-grid iteration to the multi-grid iteration is already described in § 2.5 for the one-dimensional problem. In §4.1 the algorithm is described in various ways. Typical convergence properties of the multi-grid iteration are discussed in § 4.2. The convergence rates have to be related to the computational work, which is estimated in § 4.3. Numerical results are reported in § 4.4 for the model problem of the Poisson equation in the square and in general domains.

Wolfgang Hackbusch

5. Nested Iteration Technique

Abstract

Given some iterative process, the natural approach is to start with a more or less accurate initial value u _l ⁰ and to perform several steps of the iteration.

Wolfgang Hackbusch

6. Convergence of the Two-Grid Iteration

Abstract

The two-grid iteration \(TG{M^{\left( {{\nu _1},{\nu _2}} \right)}}\) from (3.2.2) is a linear iteration having a representation (1.3.2),

$$u_l^{j + 1} = {M_l}u_l^j + {N_l}{f_l},$$

where the iteration matrix M _l depends on the numbers υ ₁ and υ ₂ : M _l = M _l (υ_l,υ₂).

Wolfgang Hackbusch

7. Convergence of the Multi-Grid Iteration

Abstract

In § 7.1 we shall prove that two-grid convergence, more precisely, the sufficient conditions from Theorem 6.1.7, almost imply the multi-grid convergence. The multi-grid contraction number is bounded by some ζ(v) < 1 with ζ (v) → 0 (o→221E;), which is independent of 1, i.e. independent of the finest step size h, and independent of the number of involved levels. However, the estimates are somewhat pessimistic. In particular, the V-cycle (cf. § 2.5) cannot be treated by this approach. § 7.2 provides sharper estimates, which apply to the V-cycle also.

Wolfgang Hackbusch

8. Fourier Analysis

Abstract

For the analysis of difference discretisations of time-dependent problems the Fourier analysis has proved as a very useful tool (cf. Richtmyer-Morton [1]). In § 2.4 we applied the Fourier analysis to a one-dimensional model problem. In this chapter the analogous analysis is performed in two dimensions.

Wolfgang Hackbusch

9. Nonlinear Multi-Grid Methods

Abstract

With the intention of not overloading the presentation with the notational and conceptual difficulties of nonlinear problems, we have so far considered only linear equations. However, it will turn out that multi-grid algorithms are perfectly suited for nonlinear boundary value problems. There are two different approaches. The first one explained in § 9.2 is based on a linearisation, thus allowing the application of linear multi-grid solvers. The remaining subsections §§ 9.3–5 are devoted to an intrinsic multi-grid treatment of non-linear problems. A third approach will be described in § 16.8.

Wolfgang Hackbusch

10. Singular Perturbation Problems

Abstract

An operator L = L(ε) depending on a parameter ε is called singularly perturbed if the limiting operator \(L(0) = \begin{array}{*{20}{c}} {\lim } \\ {\varepsilon \to 0} \end{array}L(\varepsilon )\) is of a type other than L(ε) for ε > 0. For instance, an elliptic operator L(ε) = ε L ^I + L ^II (ε > 0) is singularly perturbed if L ^II is non-elliptic or elliptic of a lower order. Different types of L ^II give rise to the subsections 10.1–3.

Wolfgang Hackbusch

11. Elliptic Systems

Abstract

In the preceding chapters only scalar differential equations Lu = f have been considered. In the present chapter it will be pointed out that the multi-grid approach applies to elliptic systems as well. In § 11.1 we introduce examples of elliptic systems. The main difficulty of the multi-grid solution is the choice of an appropriate smoother. In § 11.2 we present a smoother which is related to the Jacobi iteration for scalar problems. A counterpart of the Gauß-Seidel iteration is the distributed relaxation described in § 11.3.

Wolfgang Hackbusch

12. Eigenvalue Problems and Singular Equations

Abstract

We shall study two closely related problems: the eigenvalue problem L _l u _l = λ _l u _l , and the system L _l u _l = f _l with a singular matrix L _l .

Wolfgang Hackbusch

13. Continuation Techniques

Abstract

Instead of the elliptic equation ℒ (u) = 0 we consider the family of nonlinear equations

$$ \wp (u(\lambda ),\lambda ) = 0, $$

(13.1.1)

depending on the scalar parameter λ For ease of notation we assume that Eq. (1) is defined for λ≧O. For each λ≧O there may exist several solutions u (λ) of Eq. (1). A smooth curve (u(λ),λ)∈u×ℝ is called a solution branch. Intersection points of branches are called bifurcation points. At such points ∂ℒ(u*,λ*)/∂u is singular (see λ _A in Fig. 13.1.1). For the computation of bifurcation points we refer to § 12.5 and the approaches of Weber [1] and Mittelmann-Weber [1].

Wolfgang Hackbusch

14. Extrapolation and Defect Correction Techniques

Abstract

In § 5.4 we have already described the use of Richardson’s extrapolation from h _k−1, h _k−2 to h _k , to provide sufficiently accurate starting iterates in the nested iteration (5.4.3).

Wolfgang Hackbusch

15. Local Techniques

Abstract

In this chapter we shall discuss techniques which improve the discrete solution by locally defined discretisations. The general framework is given by the ‘local defect correction’ in § 15.1. A global discretisation of the continuous problem is completely avoided by the ‘domain decomposition methods’ studied in § 15.3.

Wolfgang Hackbusch

16. The Multi-Grid Method of the Second Kind

Abstract

Multi-grid methods were first developed for elliptic boundary value problems. However, a two-grid iteration closely related to a multi-grid algorithm for integral equations of the second kind (which we call a multi-grid iteration of the second kind) is already described in 1960 by Brakhage [1]. Abramov [1] and Sisov [1] also describe algorithms for integral eigenvalue problems that approach the two-grid idea. Atkinson [1, 2] took up the idea of Brakhage and developed automatic programs for linear integral equations.

Wolfgang Hackbusch

Backmatter