RIGOROUS QUANTITATIVE-ANALYSIS OF MULTIGRID .1. CONSTANT-COEFFICIENTS 2-LEVEL CYCLE WITH L2-NORM

Exact numerical convergence factors for any multigrid cycle can be predicted by local mode (Fourier) analysis. For general linear elliptic partial differential equation (PDE) systems with piecewise smooth coefficients in general domains discretized by uniform grids, it is proved that, in the limit of small meshsizes, these predicted factors are indeed obtained, provided the cycle is supplemented with a proper processing at and near the boundaries. That processing, it is proved, costs negligible extra computer work. Apart from mode analysis, a coarse grid approximation (CGA) conditions is introduced which is both necessary and sufficient for the multigrid algorithm to work properly. The present part studies the L2 convergence in one cycle for equations with constant coefficients. In the sequel [Brandt, Rigorous quantitative analysis of multigrid, II: Extensions and practical implications, manuscript] extensions are discussed to many cycles (asymptotic convergence), to more levels with arbitrary cycle types (V, W, etc.), and to full multigrid (FMG) algorithms. Various error norms and their relations to the orders of the intergrid transfer operators are analyzed. Global mode analysis, required to supplement the local analysis in various border cases, is developed and partial relaxation sweeps are systematically introduced into both analysis and practice.