Crosswind block iterative method for convection-dominated problems

This paper is on a block iterative algorithm for convection-dominated equations. The algorithm uses crosswind thin blocks in a block Gauss-Seidel method. The relaxation sweep is carried out successively along the downwind direction and exact solvers are used for the block systems. This method is efficient for convection-dominated problems discretized by monotone finite element/finite difference schemes, such as the edge-average finite element method. 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 analyzed 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 the 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-dominated problems and to compare it with other popular algorithms.