Two-Level Analysis and Multigrid Methods
for SPD, Non-Normal and Indefinite Problems

Yair Shapira
Computer Science Department
Haifa 32000


A convergence theory for Black-Box Multigrid for a class of SPD problems is presented. Improved versions of Black-Box Multigrid for diffusion problems with discontinuous coefficients are defined. A two-level analysis method for several automatic multigrid methods for certain separable problems is introduced. Unlike standard two-level analysis methods, based on Fourier analysis, it is based on spectral analysis, hence applicable to non-normal problems and to certain problems with variable coefficients. For indefinite problems, it provides a way to choose an optimal mesh size for the coarsest grid used and motivates the definition of an improved version of Black-Box Multigrid. Numerical experiments confirming the analysis are reported.

Contributed October 19, 1995 and updated last on November 14, 1995.