Parallel Coarse-Grid Selection and Element Interpolation for Algebraic Multigrid

Andrew J. Cleary
Robert D. Falgout
Van Emden Henson
Jim E. Jones
Lawrence Livermore National Laboratory,
Center for Applied Scientific Computing


The need to solve linear systems arising from problems posed on extremely large, unstructured grids has sparked great interest in parallelizing algebraic multigrid (AMG). The ``classical''AMG algorithm, however, selects the coarse-grid points in a manner that is inherently sequential, and no scalable way of parallelizing it is known. Unless scalable parallel coarse-grid selection algorithms are developed, coarse-grid selection could become a significant fraction of the total effort, even to the point of dominating the computation time.

In this talk we examine two important concepts. The first is the formulation of a parallel coarsening algorithm based on heuristics designed to insure coarse-grid quality by honoring the relationships of the independent variables to each other. This new technique is similar to the standard approach, but the heuristics used are modified to permit parallel processing. Experimental results are described.

The second concept is a careful examination of the fact that the underlying requirement for the coarse grid is to accurately represent ``smooth'' errors that are not reduced by relaxation. Further, the prolongation operator must be designed to transfer these components accurately to the fine grid. By using information from the finite element stiffness matrices, we develop a theory that produces the ``optimal'' prolongation for a given coarse grid, and we explore methods of using this information to select high-quality coarse grids.