Algebraic multigrid methods

DOI10.1017/S0962492917000083MaRDI QIDQ4594246zbMATH OpenOpenAlexFDO

Publication date 17 November 2017

Published in Acta Numerica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.01917

aggregation algebraic multigrid anisotropic coefficients bootstrap AMG coarse spaces coarsening strategies sparse matrix

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)

Abstract: This paper is to give an overview of AMG methods for solving large scale systems of equations such as those from the discretization of partial differential equations. AMG is often understood as the acronym of "Algebraic Multi-Grid", but it can also be understood as "Abstract Muti-Grid". Indeed, as it demonstrates in this paper, how and why an algebraic multigrid method can be better understood in a more abstract level. In the literature, there are a variety of different algebraic multigrid methods that have been developed from different perspectives. In this paper, we try to develop a unified framework and theory that can be used to derive and analyze different algebraic multigrid methods in a coherent manner. Given a smoother

R

for a matrix

A

, such as Gauss-Seidel or Jacobi, we prove that the optimal coarse space of dimension

n_{c}

is the span of the eigen-vectors corresponding to the first

n_{c}

eigenvalues of

(with

). We also prove that this optimal coarse space can be obtained by a constrained trace-minimization problem for a matrix associated with

and demonstrate that coarse spaces of most of existing AMG methods can be viewed some approximate solution of this trace-minimization problem. Furthermore, we provide a general approach to the construction of a quasi-optimal coarse space and we prove that under appropriate assumptions the resulting two-level AMG method for the underlying linear system converges uniformly with respect to the size of the problem, the coefficient variation, and the anisotropy. Our theory applies to most existing multigrid methods, including the standard geometric multigrid method, the classic AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG, and spectral AMGe.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

Describes a project that uses

Uses Software

This page was built for publication: Algebraic multigrid methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4594246)