Recently, CCMA members Jinchao Xu and Ludmil Zikatanov published a 131-page review article entitled “Algebraic Multigrid Methods” (AMG) in Acta Numerica, 26, 591-721. Acta Numerica has the highest impact factor among all mathematical journals, globally. It publishes a single issue per year and its editorial board invites leading researchers to publish review articles on various topics in numerical analysis and scientific computing. This article provides an overview of AMG methods for solving large-scale systems of equations, such as those from discretization of partial differential equations. AMG is often associated as the acronym for ‘algebraic multigrid’, but it can also represent ‘abstract multigrid’. Indeed, the authors demonstrate in this paper how and why an algebraic multigrid method can be better understood at a more abstract level. In order to derive and analyze different algebraic multigrid methods in a coherent manner, the authors develop a unified framework and theory in the paper that can be applied to understand a variety of different algebraic multigrid methods that have been developed from different perspectives for different problems. For example, given a smoother  for a matrix  , such as Gauss–Seidel or Jacobi, the authors demonstrate that the optimal coarse space of dimension  is the span of the eigenvectors corresponding to the first  eigenvectors  (with  ). The authors also prove that this optimal coarse space can be obtained via a constrained trace-minimization problem for a matrix associated with . They demonstrate that coarse spaces of most existing AMG methods can be viewed as approximate solutions of this trace-minimization problem. Furthermore, the authors provide a general approach to the construction of quasi-optimal coarse spaces and 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. The theory applies to most existing multigrid methods, including the standard geometric multigrid method, classical AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG, and spectral AMGe.

As of May 6, 2020, the paper has been cited 70 times (per scholar.google.com).

Share →

Leave a Reply

Skip to toolbar