  Algebraic Multigrid (AMG) methods are often robust and effective solvers for
solving the large and sparse linear systems that arise from discretized PDEs
and other problems, relying on heuristic graph algorithms to achieve their
performance. Reduction-based AMG (AMGr) algorithms attempt to formalize these
heuristics by providing two-level convergence bounds that depend concretely on
properties of the partitioning of the given matrix into its fine- and
coarse-grid degrees of freedom. MacLachlan and Saad (SISC 2007) proved that the
AMGr method yields provably robust two-level convergence for symmetric and
positive-definite matrices that are diagonally dominant, with a convergence
factor bounded as a function of a coarsening parameter. However, when applying
AMGr algorithms to matrices that are not diagonally dominant, not only do the
convergence factor bounds not hold, but measured performance is notably
degraded. Here, we present modifications to the classical AMGr algorithm that
improve its performance on matrices that are not diagonally dominant, making
use of strength of connection, sparse approximate inverse (SPAI) techniques,
and interpolation truncation and rescaling, to improve robustness while
maintaining control of the algorithmic costs. We present numerical results
demonstrating the robustness of this approach for both classical isotropic
diffusion problems and for non-diagonally dominant systems coming from
anisotropic diffusion.
