Ordering Techniques for Convection Dominated Problems on Unstructured Three-Dimensional Grids

Sabine Le Borne
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

E = E(G) = { (i, j) in VxV: aij != 0 }.
If the matrix A arises from a finite element discretization of a partial differential equation with continuous piecewise linear basis functions in the standard nodal basis, the vertices and edges in the triangulation correspond to the vertices and edges in the matrix graph, resp.

Typically, the size |aij| 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

E_0 = { (i, j) in E: |aij| `is large' }.

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.