
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 largescale 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, reductionbased AMG, and
sufficient conditions derived for $\ell^2$convergence of error and residual.
In particular, classical multigrid approximation properties are connected with
reductionbased measures to develop a robust framework for nonsymmetric,
reductionbased AMG.
Matrices with blocktriangular structure are then recognized as being
amenable to reductiontype algorithms, and a reductionbased 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 6thorder 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
Frelaxation. A new block decomposition of the AMG errorpropagation 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
advectiondiffusionreaction equation. lAIR is shown to be a robust solver for
various discretizations of the advectiondiffusionreaction equation, including
timedependent and steadystate, from purely advective to purely diffusive.
Convergence is robust for discretizations on unstructured meshes and using
higherorder 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 linerelaxation and
K or Wcycles 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 rootnode 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.
NonSPD 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 socalled rootnode AMG, which can be viewed as
a combination of classical and aggregationbased multigrid. An algorithm for
rootnode is outlined and a filtering strategy is developed, which is able to
control the cost of using rootnode AMG, particularly on difficult problems.
New theoretical motivation is provided for rootnode and energyminimization as
applied to symmetric as well nonsymmetric systems. Numerical results are then
presented demonstrating the robust ability of rootnode to solve nonsymmetric
problems, systemsbased problems, and difficult SPD problems, including
strongly anisotropic diffusion, convectiondiffusion, and upwind steadystate
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 rootnode AMG over alternative methods.