The Improved Robustness of Multigrid Elliptic Solvers Based on Multiple Semicoarsened Grids

Multigrid convergence rates degenerate on problems with stretched grids or anisotropic operators, unless one uses line or plane relaxation. For three-dimensional problems, only plane relaxation suffices, in general. While line and plane relaxation algorithms are efficient on sequential machines, they are quite awkward and inefficient on parallel machines. This paper presents a new multigrid algorithm, based on the use of multiple coarse grids, that eliminates the need for line or plane relaxation in anisotropic problems. This algorithm is developed, and the standard multigrid theory is extended to establish rapid convergence for this class of algorithms. The new algorithm uses only point relaxation, allowing easy and efficient parallel implementation, yet achieves robustness and convergence rates comparable to line and plane relaxation multigrid algorithms. The algorithm described here is a variant of Mulder’s multigrid algorithm [W. Mulder, J. Compact. Phys., 83 (1989), pp. 303–323] for hyperbolic problems. The latter uses multiple coarse grids to achieve robustness, and appears to work on elliptic as well as hyperbolic problems, though it is more complex than the algorithm proposed here, and its rapid convergence has never been proven. The new algorithm combines the contributions from the multiple coarse grids via a local “switch,” based on the strength of the discrete operator in each coordinate direction. This improvement allows us to show that the V-cycle convergence rate is uniformly bounded away from one, on model anisotropic problems. Moreover, the new algorithm can be combined with the idea of concurrent iteration on all multigrid levels to yield a highly parallel algorithm for strongly anisotropic problems.