Most approaches to parallelizing the coarsening phase of the classical algebraic multigrid method [Ruge and Stüben (1987)] are based on coarsening the interior of each subdomain and then utilizing an arbitration scheme along the subdomain boundaries. Often, the coarsenings along these boundaries are mismatched due to the interior coarsenings, causing poor convergence of the method and/or higher than necessary operator complexities.

Brandt [Brandt (2000)] has recently developed coarsening procedures based on "compatible relaxation." Beginning with an independent set of C-points, additional C points are added based on how quickly the these points converge in a relaxation process. We investigate other relaxation procedures for adding C points and relaxation procedures for deleting C points. This allows the coarsening process to begin with a very poor (possibly random) selection of C points. C points are then added and deleted in sequential stages. Preliminary experiments show that only a few stages are required before the coarse grid converges to a good distribution of C points. The experiments also show a potential of this method to improve the operator complexity of AMG for several types of problems.

References:

Brandt, A. (2000)

General highly accurate algebraic coarsening. Elect. Trans. Numer. Anal., 10:1--20.

Ruge, J.W. and Stüben, K. (1987)

Algebraic multigrid. In McCormick, S.F., editor, SIAM Frontiers on Applied Mathematics, Volume 3, Multigrid Methods, pages 73--130. SIAM.

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.