Downwind Gauß-Seidel Smoothing for Convection Dominated Problems

Wolfgang Hackbusch

Abstract

1 The Convection-Diffusion Equation

A typical feature of flow problems is the dominating convection. A corresponding model equation is the convection-diffusion equation

−εΔu + ⟨b, grad u⟩ = f  (1)

with a positive but small ε subject to certain boundary conditions. The equation is elliptic, but the hyperbolic character appears when ε approaches zero. It is wellknown that the discretisation of (1) requires special care in order to produce stable systems. In the following we assume that the principal part is discretised by standard linear finite elements in a triangulation of the domain. Concerning the convection term, we consider a simple upwind formulation.

2 The Multi-Grid Solution

Although ellipticity ensures a multi-grid convergence rate independent of the dimension (grid size), the rate may depend on the size of ε. Therefore, all singular perturbation problems like (1) give rise to ask for robust multi-grid versions, whose convergence rate is bounded independently of the perturbation parameter ε. The convection-diffusion equation is discussed since the beginning of multi-grid methods. However, the discussion is more or less focussed to the difference method in a regular grid under the assumption that the direction b lies in a certain angle interval. If, e.g., the x-component of b is non-negative, the lexicographical ordering is appropriate for the Gauß-Seidel smoothing, since in the limit case of ε = 0, the matrix is lower triangular and therefore the Gauß-Seidel iteration becomes an exact solver. Analogously, one needs an anti-lexicographical ordering, if b has a negative x-component. Thus, the appropriate ordering must follow the downwind direction. Difficulties arise when the direction b is a variable coefficient with quite different orientations in the domain. Another difficulty appears when the regular grid of the difference method is replaced by a general finite-element triangulation. In this case, it is not at all obvious what the counterpart of the simple lexicographical ordering in the regular finite-difference case is.

We mentioned that in the limit case ε = 0, the Gauß-Seidel smoothing with downwind numbering becomes an exact solver. If ε is of the size O(1), the coarse-grid correction is well working and ensures good convergence rates. However, with decreasing ε the coarse-grid correction becomes less effective since due to the diminishing ellipticity the correction can be assumed to smooth only in the convection direction b, but not normal to b (a possible remedy is the frequency decomposition multi-grid version).

3 Numbering and Block Partitioning

The main subject of the talk is the presentation of the numbering techniques. If no cycles arise, one gets a perfect ordering for the pointwise Gauß-Seidel process. In the more general case cycles appear, which will be handled by block partitionings. We present efficient algorithms which combine the numbering with the construction of block partitionings. The blocks are simple enough to allow the exact solution of the diagonal block. Therefore, the block-Gauß-Seidel smoothing is cheaply performable. Furthermore the properties of this smoothing procedure and other choices of block partitionings are discussed.

Although we only discuss the Gauß-Seidel smoothing, these results are also of great interest for the incomplete LU smoothers since they depend in the similar way on an appropriate ordering of the unknowns.