A crosswind block iterative method for convection-dominated problems

This paper is on a block iterative algorithm for convection-dominated equat ions. The algorithm uses crosswind thin blocks in a block Gauss{Seidel meth od. The relaxation sweep is carried out successively along the downwind dir ection and exact solvers are used for the block systems. This method is eff icient for convection-dominated problems discretized by monotone finite ele ment/finite difference schemes, such as the edge-average finite element met hod. An optimal partitioning and ordering algorithm, Tarjan's algorithm, is used to partition the nodes into crosswind blocks and order the blocks in the downwind direction. The convergence of this block iterative method is a nalyzed and exponential convergence rates are proved for both one- and two- dimensional cases on both structured and unstructured meshes. Our empirical and analytical studies indicate that crosswind grouping is essential for t he rapid convergence of the method and merely ordering the nodes along the downwind direction is not good enough. Some numerical examples are given to illustrate the effectiveness of the proposed algorithm for convection-domi nated problems and to compare it with other popular algorithms.