Generalizing reduction‐based algebraic multigrid
- 18 December 2023
- journal article
- research article
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 31 (3)
Abstract
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.Keywords
All Related Versions
Funding Information
- NSERC
This publication has 46 references indexed in Scilit:
- Parallel multigrid algorithms based on generic approximate sparse inverses: an SMP approachThe Journal of Supercomputing, 2013
- Multilevel sparse approximate inverse preconditioners for adaptive mesh refinementLinear Algebra and its Applications, 2009
- Distance‐two interpolation for parallel algebraic multigridNumerical Linear Algebra with Applications, 2007
- Adaptive reduction‐based AMGNumerical Linear Algebra with Applications, 2006
- BoomerAMG: A parallel algebraic multigrid solver and preconditionerApplied Numerical Mathematics, 2002
- Sparse approximate inverse smoothers for geometric and algebraic multigridApplied Numerical Mathematics, 2002
- A comparative study of sparse approximate inverse preconditionersApplied Numerical Mathematics, 1999
- Frequency domain behavior of a set of parallel multigrid smoothing operatorsInternational Journal of Computer Mathematics, 1990
- A note on MGR methodsLinear Algebra and its Applications, 1983
- Algebraic multigrid (AMG): experiences and comparisonsApplied Mathematics and Computation, 1983