Christian-Albrechts-University Kiel, Germany

For convection-dominated problems in two spatial dimensions, multigrid methods using a simple Gauß-Seidel method as a smoother can lead to excellent results if the unknowns are ordered appropriately.

The difficulties with constructing robust multigrid solvers in three dimensions are much greater than in two dimensions. Many ordering strategies that have been proposed for two-dimensional problems make explicit use of the planarity of the underlying graphs and are not directly applicable to three-dimensional problems.

We will use the graph of a matrix to develop and illustrate ordering
techniques for two- as well as for three-dimensional problems.
The matrix graph *G=G(A)* consists of the vertex set *V=V(G)* and
the edges

Typically, the size *|a _{ij}|* of the matrix entries varies
considerably over the grid due to the convective term. For the proposed
ordering strategies, we neglect small matrix entries and define the graph of
dominant entries as the graph with the reduced edge set

In three spatial dimensions, we have a structure consisting of vertices and edges, but, additionally, we can involve the faces of the tetrahedra. A sequence of neighbouring faces describes a surface which can be viewed as the counterpart to a (one-dimensional) path in the graph. In turn, an ordering of these surfaces in addition to an ordering within each surface defines an ordering for the vertices in the tetrahedral grid.

The proposed ordering algorithm produces a decomposition of the unknowns into disjoint blocks so that block iterative methods may be applied.