A ROOT-NODE BASED ALGEBRAIC MULTIGRID METHOD

doi:10.1137/16M1082706

A ROOT-NODE BASED ALGEBRAIC MULTIGRID METHOD

2017-01-01

22

OA

AI

T

Thomas A. Manteuffel *

DOI：10.1137/16M1082706

Original

Save

View PDF

Abstract

En 中文

This paper provides a unified 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 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 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.

Keywords:

multigrid

algebraic multigrid

root-node

energy minimization

interpolation smoothing

anisotropic diffusion

A ROOT-NODE BASED ALGEBRAIC MULTIGRID METHOD

Abstract

AI Summary

Journal

Organization