Algebraic multigrid (AMG) is often an effective solver for symmetric positive
definite (SPD) linear systems resulting from the discretization of general
elliptic PDEs, or the spatial discretization of parabolic PDEs. However,
convergence theory and most variations of AMG rely on $A$ being SPD. Hyperbolic
PDEs, which arise often in large-scale scientific simulations, remain a
challenge for AMG, as well as other fast linear solvers, in part because the
resulting linear systems are often highly nonsymmetric. Here, a novel
convergence framework is developed for nonsymmetric, reduction-based AMG, and
sufficient conditions derived for $\ell^2$-convergence of error and residual.
In particular, classical multigrid approximation properties are connected with
reduction-based measures to develop a robust framework for nonsymmetric,
Matrices with block-triangular structure are then recognized as being
amenable to reduction-type algorithms, and a reduction-based AMG method is
developed for upwind discretizations of hyperbolic PDEs, based on the concept
of a Neumann approximation to ideal restriction ($n$AIR). $n$AIR can be seen as
a variation of local AIR ($\ell$AIR) introduced in previous work, specifically
targeting matrices with triangular structure. Although less versatile than
$\ell$AIR, setup times for $n$AIR can be substantially faster for problems with
high connectivity. $n$AIR is shown to be an effective and scalable solver of
steady state transport for discontinuous, upwind discretizations, with
unstructured meshes, and up to 6th-order finite elements, offering a
significant improvement over existing AMG methods. $n$AIR is also shown to be
effective on several classes of `nearly triangular' matrices, resulting from
curvilinear finite elements and artificial diffusion.
Algebraic multigrid (AMG) solvers and preconditioners are some of the fastest
numerical methods to solve linear systems, particularly in a parallel
environment, scaling to hundreds of thousands of cores. Most AMG methods and
theory assume a symmetric positive definite operator. This paper presents a new
variation on classical AMG for nonsymmetric matrices (denoted lAIR), based on a
local approximation to the ideal restriction operator, coupled with
F-relaxation. A new block decomposition of the AMG error-propagation operator
is used for a spectral analysis of convergence, and the efficacy of the
algorithm is demonstrated on systems arising from the discrete form of the
advection-diffusion-reaction equation. lAIR is shown to be a robust solver for
various discretizations of the advection-diffusion-reaction equation, including
time-dependent and steady-state, from purely advective to purely diffusive.
Convergence is robust for discretizations on unstructured meshes and using
higher-order finite elements, and is particularly effective on upwind
discontinuous Galerkin discretizations. Although the implementation used here
is not parallel, each part of the algorithm is highly parallelizable, avoiding
common multigrid adjustments for strong advection such as line-relaxation and
K- or W-cycles that can be effective in serial, but suffer from high
communication costs in parallel, limiting their scalability.
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.