  Algebraic multigrid (AMG) is an $\mathcal{O}(n)$ solution process for many
large sparse linear systems. A hierarchy of progressively coarser grids is
constructed that utilize complementary relaxation and interpolation operators.
High-energy error is reduced by relaxation, while low-energy error is mapped to
coarse-grids and reduced there. However, large parallel communication costs
often limit parallel scalability. As the multigrid hierarchy is formed, each
coarse matrix is formed through a triple matrix product. The resulting
coarse-grids often have significantly more nonzeros per row than the original
fine-grid operator, thereby generating high parallel communication costs on
coarse-levels. In this paper, we introduce a method that systematically removes
entries in coarse-grid matrices after the hierarchy is formed, leading to an
improved communication costs. We sparsify by removing weakly connected or
unimportant entries in the matrix, leading to improved solve time. The main
trade-off is that if the heuristic identifying unimportant entries is used too
aggressively, then AMG convergence can suffer. To counteract this, the original
hierarchy is retained, allowing entries to be reintroduced into the solver
hierarchy if convergence is too slow. This enables a balance between
communication cost and convergence, as necessary. In this paper we present new
algorithms for reducing communication and present a number of computational
experiments in support.
