View article

1. Introduction. The basic multigrid principle is that the smoother damps the oscillatory high frequency errors whereas the coarse grid correction reduces the smooth low frequency errors. However, this principle may not hold for convection dominated problems since the success of the standard techniques often rely on the intrinsic properties of elliptic PDEs, for instance, symmetry and positive de niteness, which are not generally true for convection dominated problems. Several smoothing techniques have been proposed for convection dominated problems. One approach is to apply Gauss-Seidel with the so-called downwind ordering 3, 1, 6, 11, 16]. The idea is that the linear system given by the upwind discretization can be well-approximated by the lower triangular part if the unknowns are ordered according to the ow direction. Another approach is to use time-stepping methods as smoothers 7, 8, 10, 13]. The idea is that this class of smoothers do not just reduce the high frequency errors, but more importantly, also propagate the errors along the ow directions. Thus, the multigrid process can be interpreted as speeding up the error propagation by taking larger time step sizes on the coarse grids. To analyze the e ciency of multigrid methods, one must then take into account the wave propagation property. In the classical Fourier-based analysis of multigrid methods 17], only the magnitude of the Fourier error components are considered, thus ignoring completely the phase angles which account for the wave propagation 15]. Gustafsson and L otstedt 4, 12] rst analyze the phase speed of this multigrid approach, and prove that a speedup of 2K? 1 is …