Distance-Two Interpolation for Parallel Algebraic Multigrid Ulrike Yang with Rob Falgout, LLNL

Algebraic multigrid (AMG) is one of the most efficient and scalable parallel algorithms for solving sparse linear systems on unstructured grids. However, for large three-dimensional problems, the coarse grids that are normally used in AMG often lead to growing complexity in terms of memory use and execution time per AMG V-cycle. Sparser coarse grids, such as the grids obtained by the Parallel Modified Independent Set (PMIS) coarsening algorithm, remedy this complexity growth, but lead to non-scalable AMG convergence factors when traditional distance-one interpolation methods are used.

In this poster we study the scalability of AMG methods that combine PMIS coarse grids with long distance interpolation methods. AMG performance and scalability is compared for previously described long-range interpolation methods and new variants of them, for a variety of relevant test problems on parallel computers. It is shown that the increased interpolation accuracy largely restores the scalability of AMG convergence factors for PMIS-coarsened grids, and in combination with complexity reducing methods, such as interpolation truncation, one obtains a class of parallel AMG methods that enjoy excellent scalability properties on very large parallel computers.