New convergence estimates for multigrid algorithms

Abstract:

In this paper, new convergence estimates are proved for both symmetric and nonsymmetric multigrid algorithms applied to symmetric positive definite problems. Our theory relates the convergence of multigrid algorithms to a "regularity and approximation" parameter $\alpha \in (0,1]$ and the number of relaxations m. We show that for the symmetric and nonsymmetric $\mathcal {V}$ cycles, the multigrid iteration converges for any positive m at a rate which deteriorates no worse than $1 - c{j^{ - (1 - \alpha )/\alpha }}$, where j is the number of grid levels. We then define a generalized $\mathcal {V}$ cycle algorithm which involves exponentially increasing (for example, doubling) the number of smoothings on successively coarser grids. We show that the resulting symmetric and nonsymmetric multigrid iterations converge for any $\alpha$ with rates that are independent of the mesh size. The theory is presented in an abstract setting which can be applied to finite element multigrid and finite difference multigrid methods.