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

Craig C. Douglas
Mathematical Sciences Department,
IBM Research Division
Thomas J. Watson Research Center
P. O. Box 218
Yorktown Heights, NY 10598
E-mail:  bells@watson.ibm.com

Jim Douglas, Jr.
Department of Mathematics
Purdue University
Mathematical Sciences Building
West Lafayette, IN 47907
E-mail:  douglas@math.purdue.edu

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.

Keywords:  multigrid, aggregation, disaggregation

AMSMOS Classification:  65N15, 65N10