Ordering Techniques for Two- and Three-Dimensional Convection-Dominated Elliptic Boundary Value Problems

Multigrid methods with simple smoothers have been proven to be very successful for elliptic problems with no or only moderate convection. In the presence of dominant convection or anisotropies as it might appear in equations of computational fluid dynamics (e.g. in the Navier-Stokes equations), the convergence rate typically decreases. This is due to a weakened smoothing property as well as to problems in the coarse grid correction. In order to obtain a multigrid method that is robust for convection-dominated problems, we construct efficient smoothers that obtain their favorable properties through an appropriate ordering of the unknowns. We propose several ordering techniques that work on the graph associated with the (convective part of the) stiffness matrix. The ordering algorithms provide a numbering together with a block structure which can be used for block iterative methods. We provide numerical results for the Stokes equations with a convective term illustrating the improved convergence properties of the multigrid algorithm when applied with an appropriate ordering of the unknowns. Received July 12, 1999; revised October 1, 1999