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.
%0 Generic
%1 Southworth2018Nonsymmetric
%A Southworth, Ben
%A Manteuffel, Thomas A.
%A Ruge, John
%D 2018
%J arXiv.org > math > Numerical Analysis
%K 65f08-preconditioners-for-iterative-methods 65f10-iterative-methods-for-linear-systems 65m55-pdes-ibvps-multigrid-methods-domain-decomposition 65n22-pdes-bvps-solution-of-discretized-equations
%N 06065
%T Nonsymmetric Algebraic Multigrid Based on Local Approximate Ideal Restriction (lAIR)
%U http://arxiv.org/abs/1708.06065
%V 1708
%X 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.
@misc{Southworth2018Nonsymmetric,
abstract = {{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.}},
added-at = {2019-03-01T00:11:50.000+0100},
archiveprefix = {arXiv},
author = {Southworth, Ben and Manteuffel, Thomas A. and Ruge, John},
biburl = {https://www.bibsonomy.org/bibtex/2c28e50943dbcdc12135b67f7757fa24d/gdmcbain},
citeulike-article-id = {14622743},
citeulike-linkout-0 = {http://arxiv.org/abs/1708.06065},
citeulike-linkout-1 = {http://arxiv.org/pdf/1708.06065},
day = 17,
eprint = {1708.06065},
interhash = {fe189273c3470cd8de09fb4a9bfb7df4},
intrahash = {c28e50943dbcdc12135b67f7757fa24d},
journal = {arXiv.org > math > Numerical Analysis},
keywords = {65f08-preconditioners-for-iterative-methods 65f10-iterative-methods-for-linear-systems 65m55-pdes-ibvps-multigrid-methods-domain-decomposition 65n22-pdes-bvps-solution-of-discretized-equations},
month = jul,
number = 06065,
posted-at = {2018-08-07 01:46:16},
priority = {5},
timestamp = {2019-03-01T00:11:50.000+0100},
title = {{Nonsymmetric Algebraic Multigrid Based on Local Approximate Ideal Restriction (lAIR)}},
url = {http://arxiv.org/abs/1708.06065},
volume = 1708,
year = 2018
}