On three-grid Fourier analysis of multigrid

R. Wienands and C.W. Oosterlee

GMD - Institute for Algorithms and Scientific Computing (SCAI)
Schloss Birlinghoven, D-53754 Sankt Augustin, Germany


Fourier one-grid (smoothing) and two-grid analysis [1,5,6] are well-known and useful tools in the multigrid community. They yield realistic quantitative smoothing and two-grid convergence rates in the limit of small meshsize $h$, if a proper treatment of the boundary is performed [2].

Two-grid Fourier analysis transforms a two-grid iteration matrix into a block diagonal matrix from which its spectral radius is easily calculated. It is the basis for asympyotic multigrid convergence estimates. However, for several multigrid components or cycle variants the overall multigrid convergence cannot be approximated accurately by two-grid rates. For example, if one is interested in the varying performance of V- and W-cycles, of Pre- and Post-smoothing or of different smoothers on different grids one has to consider at least one additional grid.

Furthermore, one may use different discretizations on different grids. The most prominent example of this kind is Galerkin coarsening. It can be very beneficial to replace the standard $2-h$, $4-h$, etc. discretizations on the coarser grids by another variant. On the other hand, these different discretizations may introduce new problems. Investigations of the two-grid method cannot display possible smoothing difficulties or other problems on the coarser grids induced by the different discretizations, since the direct solution of the $2-h$ problem is assumed.

To capture these additional phenomena we developed a three-grid Fourier analysis tool, which is presented in this talk. In the first part we outline the theoretical background of the three-grid analysis. This analysis can be generalized to the situation where multigrid is a preconditioner for restarted GMRES in the same way as it was done in [6] for the two-grid analysis.
Instead of $(4 \times 4)$-blocks for the two-grid iteration matrix [1,5,6], the three-grid iteration matrix is transformed into a $(16 \times 16)$-block matrix by Fourier analysis in the two-dimensional scalar case. This means that the calculation of three-grid aymptotic convergence rates is reduced to the calculation of the spectral radii of certain $(16 \times 16)$-matrices.

In the second part of the talk we apply the three-grid analysis to several equations and multigrid components. We focus on nonelliptic or singular pertubation problems like the convection diffusion equation discretized by first or higer order upwind discretizations or the rotated anisotropic diffusion equation. For these problems a variety of non standard coarse grid discretizations is evaluated. Some of them are discussed in [7]. For example Galerkin coarsening based on the transfer operators from [3] is investigated. Furthermore we consider several combinations of higher-order discretizations of the indefinite Helmholtz equation [4].
We would like to emphasize that the different multigrid algorithms are not only evaluated as a solver but also as a preconditioner for restarted GMRES [6]. The Fourier results are confirmed by numerical experiments.

[1] A. Brandt, Multi-level adaptive solutions to boundary-value problems. Math. Comp. 31, 333-390 (1977).
[2] A. Brandt, Rigorous quantitive analysis of multigrid, I: Constant coefficients two-level cycle with $L_2$-norm. SIAM J. Numer. Anal. 31, 1695-1730 (1994).
[3] J.E. Dendy Jr., Blackbox multigrid for nonsymmetric problems. Appl. Math. Comput. 13, 261-283, (1983).
[4] I. Singer and E. Turkel, Higher order finite difference methods for the Helmholtz equation. Computer Methods in Applied Mechanics and Engineering 163, 343-358 (1998).
[5] K. St\"uben and U. Trottenberg, Multigrid methods: fundamental algorithms, model problem analysis and applications. In: W.Hackbusch and U. Trottenberg (eds.), Multigrid Methods, Lecture Notes in Math. 960, 1-176, Springer, Berlin Germany (1982).
[6] R. Wienands, C.W. Oosterlee and T. Washio, Fourier analysis of GMRES($m$) preconditioned by multigrid. to appear in SIAM J. Sci. Comput. (2000).
[7] I. Yavneh, Coarse-grid correction for nonelliptic and singular pertubation problems. SIAM J. Sci. Comput. 19, 1682-1699 (1998).