Charles Explorer logo
🇬🇧

Stopping criteria and recycling strategies for coarsest grid solvers in multigrid V-cycle method

Publication at Faculty of Mathematics and Physics |
2022

Abstract

Multigrid methods are frequently used when solving systems of linear equations, applied either as standalone solvers or as preconditioners for iterative methods. Within each cycle, the approximation is computed using smoothing on fine grids and solving on the coarsest grid.

With growth of the size of the problems that are being solved, the size of the problems on the coarsest grid is also growing and their solution can become a computational bottleneck. In practice the problems on the coarsest grid are often solved approximately, for example by Krylov subspace methods or direct methods based on low rank approximation; see, e.g., [M. Huber, Massively parallel and fault-tolerant multigrid solvers on peta-scale systems, Ph.D. Thesis, Technical University of Munich, Germany, 2019], [Buttari et al., Numerical Linear Algebra with Applications (2021)]. The accuracy of the coarsest grid solver is typically determined experimentally in order to balance the cost of the solves and the total number of multigrid cycles required for convergence. Since the coefficient matrix of the problems on the coarsest grid remains static throughout the multigrid cycles, the concept of recycling may be used to accelerate the computation.

In the first part of the talk, we present an approach to analyzing the effect of approximate coarsest grid solves in the multigrid V-cycle method for symmetric positive definite problems. The results are further used to discuss effective stopping criteria for the coarsest grid solvers. In the second part of the talk, we discuss different recycling strategies for coarsest grid solvers based on Krylov subspaces. The results are illustrated through numerical experiments.