A root-node-based algebraic multigrid method

This paper provides a uniffied and detailed presentation of root-node-style algebraic multigrid (AMG). AMG 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 (SPD) matrices, 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 AMG is outlined, and afiltering 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 nonsymmetric systems. Numerical results are then presented demonstrating the robust ability of root-node AMG to solve nonsymmetric 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 phases are given for each example, providing additional support for root-node AMG over alternative methods.