Unified convergence theory for abstract multigrid or multilevel algorithms, serial and parallel

Abstract

Multigrid methods are analyzed in the style of standard iterative methods. A basic error bound is derived in terms of residuals on neighboring levels. The terms in this bound derive from the iterative methods used as smoothers on each level and the operators used to go from a level to the next coarser level. This bound is correct whether the underlying operator is symmetric or nonsymmetric, definite or indefinite, and singular or nonsingular. This paper allows any iterative method as a smoother (or rougher) in the multigrid cycle. While standard multigrid error analysis typically assumes a specific multigrid cycle (e.g., a V, W, or F cycle), analysis for arbitrary multigrid cycles, including adaptively chosen ones, is provided. This theory applies directly to aggregation-disaggregation methods used to solve systems of linear equations.