The notion of compatible relaxation (CR) was introduced by Brandt in [1] as a modified relaxation scheme that keeps the coarse-level variables invariant. Brandt stated that the convergence rate of CR is a general measure for the quality of the set of coarse variables. A supporting theory for these ideas was presented in [2], from which we developed a CR-based algebraic coarsening algorithm for use in algebraic multigrid (AMG) methods. In [3], a new sharp convergence theory was developed for AMG. The form of this new theory bears a striking resemblance to its predecessor and suggests the possibility of improving the CR measure.

In this talk, we will use the relationship between these two theories to motivate a new approach for CR, one that has the potential of being a sharper measure of coarse grid quality and a better predictor of AMG convergence (one specific version of this method was suggested by Livne [4]). We will discuss the theoretical properties of the new method, provide some numerical results, and discuss open questions and future directions.

This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.

[1] A. Brandt, General highly accurate algebraic coarsening, Electronic Transactions on Numerical Analysis, 10 (2000), pp. 1-20.
[2] R. D. Falgout and P. S. Vassilevski, On Generalizing the AMG Framework, SIAM J. Numer. Anal., 42 (2004), pp. 1669-1693.
[3] R. D. Falgout, P. S. Vassilevski, L. T. Zikatanov, On Two-Grid Convergence Estimates, Numer. Linear Algebra Appl., to appear.
[4] O. E. Livne, Coarsening by Compatible Relaxation, Numer. Linear Algebra Appl., 11 (2004), pp. 205-227.