An abstract method for extending two-level preconditioners
to multilevel preconditioners of comparable quality

Andrei Draganescu
Sandia National Laboratories, Optimization/Uncertainty Estimation Department
P.O. Box 5800, MS. 1110, Albuquerque NM 87185-1110
aidraga@sandia.gov indexindex

We present an abstract method for designing a multilevel preconditioner given a two-level preconditioner for an operator with positive definite symmetric part.

If we denote by $ A_{\mathrm{fine}}$ and $ A_{\mathrm{coarse}}$ two discrete versions of a continuous operator, then a two-level preconditioner $ T_{\mathrm{fine}}$ for $ A_{\mathrm{fine}}$ can be described in general by a function $ T_{\mathrm{fine}} = {\mathcal F}(A_{\mathrm{coarse}}^{-1}$, $ A_{\mathrm{fine}})$, where it is assumed that the evaluation of $ {\mathcal F}$ requires a level-independent number of applications of $ A_{\mathrm{fine}}$ and $ k$ applications of $ A_{\mathrm{coarse}}^{-1}$ ($ k=1$ or $ 2$). The natural extension to a multilevel preconditioner, consisting in replacing in $ T_{\mathrm{fine}}$ the call to $ A_{\mathrm{coarse}}^{-1}$ with a recursive call to $ {\mathcal F}$, is known to sometimes produce multilevel preconditioners of lower quality (e.g., for certain types of inverse problems). Based on the idea that inverting $ A_{\mathrm{fine}}$ essentially means to solve the nonlinear equation $ X^{-1} - A_{\mathrm{fine}}= 0$, we define our multigrid preconditioner to be the first Newton iterate of the map $ X\mapsto X^{-1} - A_{\mathrm{fine}}$ starting at the ``natural'' multilevel preconditioner. For $ k=1$, the resulting algorithm has a W-cycle structure, and differs only slightly from the textbook version of the W-cycle. Moreover, the method guarantees that the resulting preconditioner maintains the approximation quality of the initial two-level preconditioner. The quality of approximation is measured using a certain distance function, which determines the degree to which two operators with positive definite symmetric parts are spectrally equivalent. We apply this method to designing and analyzing a multigrid preconditioner for a linear advection-diffusion-reaction equation.

Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed-Martin Company, for the United States Department of Energy under Contract DE-AC04-94AL85000.