A Root-Node Based Algebraic Multigrid Method

Abstract

This paper provides a unified and detailed presentation of root-node style algebraic multigrid (AMG). Algebraic multigrid is a popular and effective iterative method for solving large, sparse linear systems that arise from discretizing partial differential equations. However, while AMG is designed for symmetric positive definite matrices (SPD), certain SPD problems, such as anisotropic diffusion, are still not adequately addressed by existing methods. Non-SPD problems pose an even greater challenge, and in practice AMG is often not considered as a solver for such problems. The focus of this paper is on so-called root-node AMG, which can be viewed as a combination of classical and aggregation-based multigrid. An algorithm for root-node is outlined and a filtering strategy is developed, which is able to control the cost of using root-node AMG, particularly on difficult problems. New theoretical motivation is provided for root-node and energy-minimization as applied to symmetric as well non-symmetric systems. Numerical results are then presented demonstrating the robust ability of root-node to solve non-symmetric problems, systems-based problems, and difficult SPD problems, including strongly anisotropic diffusion, convection-diffusion, and upwind steady-state transport, in a scalable manner. New, detailed estimates of the computational cost of the setup and solve phase are given for each example, providing additional support for root-node AMG over alternative methods.

35 pages, 10 figures

References in corpus (1)

• Algebraic distance for anisotropic diffusion problems: multilevel results

Cited by in corpus (10)

• MFEM: a modular finite element methods library
• Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems
• A Weighted Least-Squares Transport Equation Compatible with Source Iteration and Voids
• Mixed $(\mathcal{L}{\mathcal{L}}^{\ast }{)}^{-1}$ and $\mathcal{L}{\mathcal{L}}^{\ast }$ least-squares finite element methods with application to linear hyperbolic problems
• A Least-Squares Finite Element Method Based on the Helmholtz Decomposition for Hyperbolic Balance Laws
• Parallel Energy-Minimization Prolongation for Algebraic Multigrid
• AIR algebraic multigrid for a space-time hybridizable discontinuous Galerkin discretization of advection(-diffusion)
• Nonsymmetric Algebraic Multigrid Based on Local Approximate Ideal Restriction (lAIR)
• The Role of Energy Minimization in Algebraic Multigrid Interpolation
• Convergence in Norm of Nonsymmetric Algebraic Multigrid