A Unified Convergence Theory for Abstract Multigrid or Multilevel
Algorithms, Serial and Parallel

Craig C. Douglas
IBM T. J. Watson Research Center
Yorktown Heights, NY, USA and
Computer Science Department
Yale University
New Haven, CT, USA

Jim Douglas, Jr.
Department of Mathematics
Purdue University
Mathematical Sciences Building
West Lafayette, IN 47907, USA

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. We allow 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.

Key words: multigrid, aggregation, disaggregation

AMSMOS Classification: 65N15, 65N10


Contributed April 4, 1992.