On Ordering Strategies for Multigrid Methods

Thomas Probst
University of Kiel, Mathematical Seminar II
Hermann-Rodewald-Str. 3,
D-24098 Kiel, Germany


While multigrid methods are fast for the iterative solution of ``well behaving'' elliptic problems, their convergence rate deteriorates in the case of dominant convection, mainly due to the loss of the smoothing property. Another, similar case of smoothing failure is the occurrence of anisotropy, which is caused either by the equation itself or by the geometric structure (grid/triangulation) which underlies the discretisation.

When one uses finite element methods with piecewise linear functions on a triangulation, the unknowns of the discretisation correspond to the corners of the triangles/tetrahedra.

It is important to notice that in the case of dominant convection the equation also changes its character: from elliptic to hyperbolic. This gives hints for the process of the solution of the arising linear system: methods following the characteristics are appropriate.

Algebraically, this corresponds to a reordering of the unknowns and the application of smoothing methods like Gau{\ss}-Seidel smoothing which can be almost an exact solver if applied to upper (lower) triangular matrices While reordering has been carefully studied when dealing with noncircular flow fields, circular flow needs an appropriate block partioning.

If anisotropy occurs, unknowns of spatial dimension may be decoupled, and instead of one 3D problem one is faced with several 2D problems which should be treated separately. In the process of numerical solution, this corresponds to nonoverlapping block partionings. The situation becomes more complicated if the direction of anisotropy varies over the domain.

The idea to find this block partionings is to analyse the structure of the underlying matrix graph and use graph theoretical methods to find unknowns which are strongly coupled and should be treated together.

We propose reordering and block partioning algorithms, which, in connection with suitable (block) iterations, can compensate the smoother's failure.