PaperlayerView exact revision on arXiv

Source-linked AI summary

Algebraic Multigrid Methods

Jinchao Xu, Ludmil T Zikatanov

arXiv:1611.01917v2math.NA

TL;DR

AMG methods lack a broadly coherent theoretical foundation and geometric grids are often unavailable. This paper develops a unified framework for deriving and analyzing AMG methods, characterizes optimal coarse spaces through low-end eigenvectors and trace minimization, and proves uniform two-level convergence under appropriate assumptions.

  • Problem

    AMG lacks a coherent theoretical understanding, while geometric multigrid depends on geometric hierarchies that may be unavailable.

    Source: §1 · pp. 4–5

  • Method

    The paper unifies AMG analysis by characterizing optimal coarse spaces spectrally, recasting them as trace-minimization problems, and constructing quasi-optimal approximations.

    Source: §1 · p. 6

  • Results

    Under appropriate assumptions, the resulting two-level AMG method converges uniformly with respect to problem size, coefficient variation, and anisotropy.

    Source: §12.4 · p. 98

  • Takeaways & Limitations

    The framework provides a common theoretical basis for understanding and designing coarse spaces across multiple AMG and related multigrid methods.

    Source: §1 · pp. 6–7

    The presentation is incomplete because it includes only AMG algorithms fitting the paper’s frameworks, excluding bootstrap and adaptive AMG.

    Source: §16 · p. 117

Abstract

from arXiv · show

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 $\bar RA$ (with $\bar R=R+R^T-R^TAR$). We also prove that this optimal coarse space can be obtained by a constrained trace-minimization problem for a matrix associated with $\bar RA$ 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.

1. Introduction · 2. Model problems and discretization

The paper develops a unified theoretical framework for algebraic multigrid, focusing on quasi-optimal coarse spaces and their construction. It establishes the model-problem, discretization, and spectral foundations needed to analyze these methods, including finite-element operator properties and isotropic and anisotropic cases.

1. Introduction

  • AMG generalizes geometric multigrid when geometric grid hierarchies are unavailable, while seeking a coherent theoretical account of its varied algorithms.GMG combines local relaxation with coarse-grid correction but depends on readily available geometric grids; AMG extends these ideas to potentially unstructured discretizations.Source: §1 · pp. 4–5

1 INTRODUCTION

  • The analysis treats symmetric semi-positive definite systems, a broader class than the SPD systems commonly targeted by AMG.SSPD systems also represent local Neumann subproblems that help expose the intrinsic structure of AMG ideas.Source: §1 · p. 5
  • For a fixed smoother, AMG seeks a coarse space complementing the algebraic high frequencies; its optimal two-level space is the low-end eigenspace, approximated in practice by quasi-optimal spaces.The paper develops trace- and energy-minimization approaches and local eigenspace constructions, relating classical, aggregation-based, geometric, and spectral AMG methods within this framework.Source: §1 · pp. 5–7

2.1. Model elliptic PDE operators

  • The model problems are second-order elliptic boundary-value equations on bounded domains in dimensions d = 1, 2, 3, with mixed, Dirichlet, or Neumann boundary conditions.The discussion includes isotropic Poisson problems, discontinuous coefficient jumps, and anisotropy, with small ϵ used to study robustness to these effects.Source: §2 · p. 8, §2.1 · pp. 8–9

2.2. Examples of finite difference and finite element discretizations

  • Finite difference and finite element discretizations convert the model elliptic problems into sparse linear systems, including five- and nine-point Poisson schemes and stiffness-matrix formulations.Finite element discretization uses piecewise-polynomial spaces on triangulations, while the resulting stiffness matrix can coincide with a finite difference matrix on special uniform meshes.Source: §2.2 · pp. 10–11

2.3 Spectral properties

  • The discretization framework also specifies mesh regularity and introduces spectral analysis through the Courant-Fischer min-max principle for symmetric operators and matrices.Shape-regular and quasi-uniform meshes provide geometric assumptions, while ordered eigenvalues and eigenvectors support the spectral arguments used later.Source: §2.2 · p. 11, §2.3 · p. 12

2.3. Spectral properties

  • The spectral analysis recalls Ky-Fan trace minimization and characterizes PDE operators by complete eigenfunctions, nonnegative eigenvalues, and boundary-condition-dependent lowest modes.For pure Neumann problems, the first eigenvalue is zero with a constant eigenfunction; for pure Dirichlet problems, the first eigenvalue is positive and simple.Source: §2.3 · pp. 12–13
  • Finite-element discretizations on quasi-uniform meshes inherit a discrete version of Weyl’s law for their operator eigenvalues.The discretized operator L_h is defined through the finite-element bilinear form, and the estimates hold for every index 1 ≤ k ≤ N with a constant independent of k.Source: §2.3 · p. 13

2.4. Properties of finite element matrices

  • Finite-element stiffness matrices are sparse with O(N) nonzeros, symmetric positive definite under Dirichlet and mixed boundary conditions, semidefinite for pure Neumann conditions, and governed by discrete Weyl-law eigenvalue behavior.The remainder of the section specializes to pure Dirichlet boundary conditions and discusses condition numbers and refined spectral properties.Source: §2.4 · p. 14
  • For the anisotropic model matrix, the eigenvalues are λ_ij(A) = 4ϵ sin^2(iπ / 2(n + 1)) + 4 sin^2(jπ / 2(n + 1)).The matrix is represented using Kronecker-sum structure, with component eigenvalues specified for B and C.Source: §2.4 · pp. 14–15

3. Linear vector spaces and duals

The section establishes the dual-space, inner-product, matrix-representation, and spectral conventions used to formulate algebraic multigrid methods abstractly. It distinguishes operators from their coordinate matrices and clarifies finite-element subtleties involving dual bases, mass matrices, and generalized eigenproblems.

3.1. Dual and inner product

  • The framework identifies finite-dimensional V with its dual V′ through the Riesz representation theorem, while using inner products for exposition but not for infinite-dimensional identification.Abstract iterative-method discussions can instead use the dual pairing ⟨·,·⟩ directly.Source: §3.1 · pp. 15–16
  • Dual bases support theoretical matrix derivations, whereas actual algorithms use the original spaces and basis representations without explicitly implementing dual basis functions.For finite-element spaces, dual basis functions are generally globally supported and differ from nodal basis functions.Source: §3.1 · p. 16

3.2. Matrix representation

  • A subspace inclusion is represented by a prolongation matrix P, whose dual inclusion has matrix P^T with respect to the corresponding primal and dual bases.The columns of P express coarse-space basis functions in the fine-space basis.Source: §3.2 · p. 17

3.2 Matrix representation

  • Because V serves as both domain and identified dual range, an operator has distinct representations using the same primal basis or a primal-domain/dual-range basis, yielding stiffness and mass matrices.The discussion argues that introducing a discrete L2 inner product is unnecessary when the underlying operator is viewed abstractly.Source: §3.2 · p. 18

3.3. Eigenvalues and eigenvectors

  • Eigenvalues must be defined carefully for operators mapping V to V′; after suitable identification, their matrix forms produce the generalized eigenvalue problems used in finite-element analysis.Although identified pointwise, A and the identified operator have different ranges and matrix representations.Source: §3.3 · pp. 19–20

3.4. Bibliographical notes

  • These distinctions provide the conceptual foundation for the paper’s abstract presentation of algebraic multigrid methods.The authors emphasize that clarifying dual spaces, representations, and spectra resolves subtleties needed later; related background is cited to Halmos 1974, Xu 1992, and Xu 2016.Source: §3.3 · p. 20, §3.4 · p. 20

4. Basic iterative methods

The section develops linear iterative methods through approximate-inverse updates, symmetrization, and Jacobi/Gauss-Seidel smoothers. It then presents subspace corrections as an abstract framework encompassing these methods and extending to multigrid and domain decomposition.

4.1. Basic iterative methods

  • Linear iteration updates u_m from u_{m−1} using a preconditioner B applied to the residual f−Au_{m−1}, with B acting as an approximate inverse of A.The general iteration is u_m = u_{m−1} + B(f−Au_{m−1}).Source: §4.1 · p. 20
  • Symmetrizing a nonsymmetric iteration yields an equivalent update with operator B̄, and convergence is characterized by positivity of B̄ or G ≡ (B′)^−1 + B^−1 − A.The stated equivalence is ρ(I−B̄A) < 0 ⇔ B̄ > 0 ⇔ G > 0.Source: §4.1 · pp. 20–21

4.2. Jacobi and Gauss-Seidel methods

  • Modified Jacobi and Gauss-Seidel methods are specific instances of the general iteration, with convergence conditions established for modified Jacobi and Gauss-Seidel.The presentation assumes a suitable ω for modified Jacobi and sets ω = 1 for Gauss-Seidel; the methods also extend straightforwardly to block matrices.Source: §4.2 · p. 21, §4.3 · p. 22

4.3. The method of subspace corrections

  • Subspace corrections decompose V through auxiliary spaces V_i, equip each with an energy inner product and approximate local inverse, and define parallel or successive corrections.The parallel method uses B = B_psc, while successive corrections apply local updates sequentially and correspond to B = B_ssc.Source: §4.3 · pp. 22–23

4.3 The method of subspace corrections

  • Under SPD local solvers, subspace-correction theory provides a unique minimizer and estimates whose constants depend only on overlap topology, including anisotropic and jump-coefficient problems.The section also states that the results extend from SPD to symmetric, semi-positive definite operators under additional diagonal and local-SPD assumptions.Source: §4.3 · pp. 23–26

4.4. Bibliographical notes

  • The bibliographical notes identify subspace corrections as an abstract framework for iterative algorithms, while multigrid coarse spaces should approximate the low spectrum of the relaxed matrix B̄A or D^−1A.This low-spectrum component is commonly described as the near-null space.Source: §4.4 · pp. 26–27

5. Abstract multigrid methods and 2-level theory

This section develops an abstract two-level AMG framework and convergence theory centered on coarse-space design, optimality, and the capture of components that smoothers do not effectively damp. It also derives quasi-optimal coarse spaces and situates the results within prior two-level and multilevel analyses, while noting the difficulty of general uniform multilevel theory.

5.1. A two-level method

  • A two-level AMG method combines a smoother, a coarse space with prolongation, and a coarse solver; its action applies coarse-grid correction followed by post-smoothing.The method is formulated through an approximate inverse or preconditioner B, with exact coarse solves used for analysis and recursive approximations used in multilevel settings.Source: §5.1 · pp. 28–29

5.2 An optimal two-level AMG theory

  • For a fixed smoother, the optimal n_c-dimensional coarse space is spanned by eigenvectors associated with the first n_c eigenvalues of the smoother-dependent operator R̄A.The same optimal space minimizes the relevant convergence quantity and, under the stated conditions, solves a constrained trace-minimization problem; computing these eigenvalues is expensive but the result guides AMG design.Source: §5.2 · pp. 30, 32, 33

5.3 Quasi-optimal theories

  • Two-level convergence is quantitatively controlled by K(V_c), and uniform convergence follows when K(V_c) remains uniformly bounded with respect to mesh parameters.The theory provides an explicit convergence estimate, while the optimal coarse space minimizes K(V_c).Source: §5.3 · pp. 34–35

5.3. Quasi-optimal theories

  • When R̄^-1 is difficult to use, replacing it with a spectrally equivalent SPD operator D yields a practical quasi-optimal theory whose rate is governed by K(V_c,D) when equivalence constants are uniform.The framework allows simpler equivalent norms, including diagonal-based norms associated with Jacobi for symmetric Gauss-Seidel smoothers.Source: §5.3 · p. 35

5.4 Algebraically high and low frequencies

  • The framework constructs approximate optimal coarse spaces from operators A_M and D_M satisfying size-independent spectral-equivalence conditions, with Theorem 5.11 giving a resulting coarse-space criterion.These operators define algebraic high- and low-frequency structure used in most AMG coarse-space constructions.Source: §5.4 · p. 36
  • Algebraically smooth errors are those not effectively damped by the smoother and therefore must be approximated well by the coarse space.The algebraically smooth set is generally an ellipsoid rather than a linear space, and its interpretation guides robust AMG construction.Source: §5.4 · pp. 36–37

5.5 Smoothing properties of Jacobi and Gauss-Seidel methods

  • Algebraic low frequencies can be geometrically oscillatory, so geometric smoothness does not reliably identify the error components requiring coarse-grid representation.For anisotropic problems, the relevant eigenfunctions can oscillate strongly in the x-direction while remaining algebraically low-frequency.Source: §5.5 · p. 38, §5.6 · p. 40

5.6. Convergence theory in view of algebraic high- and low-frequencies

  • Under a stable decomposition into a coarse space and algebraically high-frequency subspace, the resulting two-level AMG method satisfies the section’s convergence estimate.The theory uses algebraic high- and low-frequency notions to formulate sufficient conditions for two-level convergence, and also identifies near-null spaces through low eigenvalues of the symmetrized smoother operator.Source: §5.5 · p. 38, §5.6 · p. 40

5.7. Bibliographical notes

  • Earlier work established algebraic and variational two-level theory, while sharper bounds followed from abstract subspace-correction frameworks; general algebraic multilevel convergence remains difficult and often relies on restrictive or geometric assumptions.The section also records rigorous multilevel results for selected finite-element, adaptive, and tree-based settings.Source: §5.7 · pp. 41–42

6. A general approach to the construction of coarse space

This section presents an abstract framework for constructing coarse spaces through space decompositions and subspace corrections, supported by technical analytic results.

6. A general approach to the construction of coarse space

  • The framework constructs coarse spaces using space decomposition and subspace corrections.Source: §6 · p. 42
  • The section introduces technical results that serve as analytic tools for the subsequent development.Source: §6 · p. 42
  • A stated result identifies a unique minimizer, while Lemma 6.2 assumes two conditions for Π.Source: §6 · p. 42

1. For all v

This section states the Fictitious Space Lemma and sets up the assumptions, auxiliary operators, projections, and coarse-space conditions used in its application.

Fictitious Space Lemma

  • The Fictitious Space Lemma applies when the operator Π satisfies two stated conditions.The result is presented as a direct consequence of Lemma 6.2.Source: §1 · p. 43

Auxiliary spaces

  • The framework introduces spaces V1, V2, ..., VJ related to V by linear operators, without requiring them to be subspaces of V.It also assumes that V is a sum of subspaces satisfying conditions (4.12) and (4.13).Source: §1 · p. 43

Auxiliary operators

  • Each auxiliary space has a symmetric positive-semidefinite operator Aj and a symmetric positive-definite operator Dj.These operators provide the algebraic structure used for the auxiliary-space construction.Source: §1 · p. 44

Coarse-space construction

  • The construction associates coarse spaces Vc,j with the auxiliary spaces and defines corresponding Dj-orthogonal projections Qj.A global coarse space Vc is then defined from these components.Source: §1 · p. 44

Stability assumptions

  • The assumptions require projection and approximation inequalities with positive constants, together with N(Aj) ⊂ Vc for every j.These conditions provide the stated stability requirements for the auxiliary-space framework.Source: §1 · p. 44

6 A GENERAL APPROACH TO THE CONSTRUCTION OF COARSE SPACE

The section develops a general coarse-space construction and derives two-level AMG convergence from assumptions controlling the associated approximation estimates. It also places the framework in relation to fictitious-space, auxiliary-space, AMG, and domain-decomposition literature.

6 A GENERAL APPROACH TO THE CONSTRUCTION OF COARSE SPACE

  • The construction introduces the product space V_c × V_1 × V_2 × · · · × V_J and the corresponding natural inclusion and additive preconditioner.These definitions provide the framework for applying the fictitious-space argument to the coarse-space analysis.Source: §6 · pp. 45–46
  • Under Assumptions 6.9 and 6.10, Lemmas 6.6 and 6.7 establish the required auxiliary estimates, with constants depending on C_p,1, C_p,2, µ_c, and c_D.Lemma 6.7 specifically gives a constant depending on C_p,2 and c_D, while Lemma 6.6 provides the complementary estimate involving C_p,1, C_p,2, µ_c, and c_D.Source: §6 · p. 46
  • Under Assumption 6.9, the two-level AMG method with the coarse space defined in (6.13) converges at a rate bounded by 1 − µ_c/(C_p,1 C_p,2 c_D).The convergence result follows by combining the error estimate in Theorem 6.5 with the general convergence theorem.Source: §6 · p. 46

6.1. Bibliographical notes

  • The bibliographical notes connect the framework to fictitious-space and auxiliary-space methods, and indicate applications to classical AMG, smoothed aggregation AMG, spectral AMGe, and domain-decomposition coarse spaces.The cited domain-decomposition literature uses related local eigenspace techniques for constructing coarse spaces.Source: §6.1 · pp. 46–47

7. Graphs and sparse matrices

This section introduces graph concepts used to represent sparse matrices and develops M-matrix relatives as spectrally equivalent tools for AMG finite-element matrices. It also notes that M-matrix structure alone may not ensure uniform two-level convergence when near-kernel information is lost.

7.1. Sparse matrix and its adjacency graph

  • Sparse matrices are represented by undirected adjacency graphs whose vertices index matrix rows and whose connectivity characterizes irreducibility, while graph structure supplies combinatorial rather than geometric information.The section defines adjacency, paths, connectivity, neighborhoods, degrees, distances, diameter, and independent sets for these graphs.Source: §7.1 · p. 48

7.2. M-matrix relatives of finite element stiffness matrices

  • AMG algorithms commonly filter positive-semidefinite matrices into M-matrix relatives because these relatives underpin coarse-space definitions and convergence-rate estimates.The defining inequalities compare the quadratic forms and diagonals of the relative and original matrices, and the diagonal equivalence follows for the finite-element construction.Source: §7.2 · pp. 50, 52
  • For linear finite-element stiffness matrices, an M-matrix relative is spectrally equivalent to the original matrix, has a connected graph, and supports equivalent diagonal estimates for AMG analysis.The relative is formed by removing positive off-diagonal entries and adding them to the diagonal; the equivalence constants depend only on mesh shape regularity.Source: §7.2 · pp. 51–52

7.3. Bibliographical notes

  • M-matrix properties and existence of a relative are not sufficient for uniform two-level AMG convergence if rescaling removes the constant from the operator’s kernel.The section identifies adaptive AMG as one way to recover the missing near-kernel information.Source: §7.3 · p. 52

8. Strength of connections

This section explains how strength of connection guides AMG coarsening by identifying vertices that can be aggregated or removed while preserving algebraically smooth modes. It develops symmetric and theoretically motivated strength functions alongside classical, local-optimization, and test-vector-based alternatives.

8. Strength of connections

  • Strength of connection guides coarsening by preserving algebraically smooth behavior while aggregating strongly connected vertices or linking deleted vertices to retained ones.Weak edges are removed first, then vertices are aggregated or selected through an MIS; the resulting strength also controls prolongation sparsity and the trade-off between approximation quality and cost.Source: §8 · p. 52, §8.1 · pp. 52–54

8.1. Basic idea and strength function

  • Symmetric strength functions are used theoretically because convergence is analyzed through the symmetrized smoother, even though classical directed definitions may produce nonsymmetric graphs.For M-matrices, larger |a_ij| indicates slower variation of algebraically smooth errors across an edge, motivating threshold-based connection measures.Source: §8.1 · pp. 53–54

8.2. Classical AMG

  • Classical AMG strength measures are symmetrized heuristic variants and may ignore nonnegative stiffness-matrix entries.The section notes that choosing prolongation sparsity is crucial: denser interpolation improves coarse-space approximation, whereas sparser interpolation reduces cost.Source: §8.1 · p. 54, §8.2 · p. 55

8.3. Local-optimization strength function

  • For each index pair {i,j}, pair-associated spaces and coarse spaces are defined using operators and eigenvectors; direct computation gives the strength function 1 − s1^2, with s1 = |aij|/sqrt(aii ajj).Source: §8.3 · pp. 55–56

8.4. Lean AMG

  • Lean AMG measures strength through affinity in smoothed random test vectors, whose entries should be close at strongly connected vertices.It generates K test vectors by applying ν Gauss-Seidel sweeps to Ax = 0 from random initial vectors, then compares the corresponding rows of the test-vector matrix.Source: §8.4 · p. 57

8.5. Bibliographical notes

  • The section argues that strength-of-connection heuristics, historically given limited theoretical backing, can be justified by local Poincaré inequalities and theoretically derived strength functions.It also situates these ideas among classical, aggregation, matching, and smoothed-test-vector approaches.Source: §8.5 · pp. 57–58

9. Coarsening strategies

Coarsening constructs a sequence of coarse spaces or prolongation matrices that approximate error components poorly reduced by the smoother. The section motivates an abstract, degree-of-freedom-based construction and outlines the algebraic steps used to build and recursively apply coarse operators.

9. Coarsening strategies

  • Coarsening seeks a subspace Vc whose coarsened solution approximates algebraically smooth error components that the smoother reduces poorly.Once a smoother is chosen, identifying a sequence of coarse spaces, equivalently prolongation matrices, is the central AMG task.Source: §9 · p. 58

9.1. Motivations

  • AMG reverse-engineers geometric refinement without a prescribed hierarchy, constructing coarse spaces by first identifying their dual basis of degrees of freedom.This approach is described as more intrinsic and general, while geometric examples connect coarse-grid vertices with maximal independent sets.Source: §9.1 · p. 59

9.2 Basic approach

  • The algebraic coarsening pipeline filters weak graph connections, selects coarse degrees of freedom by MIS or aggregation, constructs and postprocesses a tentative coarse space, and forms Ac = P^TAP recursively.Classical AMG uses an MIS of the filtered graph, whereas aggregation AMG greedily agglomerates neighboring points.Source: §9.2 · p. 60

9.2.1. Construction of (V′)c

  • The construction of (V′)c is formulated for a matrix A ∈ R^n×n together with its associated graph G = (V, E).The subsection introduces this graph-based setting after the general coarsening pipeline.Source: §9.2.1 · p. 61

1. Form the following two non-overlapping decompositions

This section develops AMG coarse-space construction through complementary decompositions and aggregation-based coarsening strategies, including graph-based, MIS, smoothing, matching, parallel, and adaptive approaches. It also relates these constructions to convergence control and surveys their broader methodological context.

9.2.2. Construction of V_c

  • A nonsingular Gramm matrix yields a pre-coarse space W_c with V = V_hf ⊕ W_c, providing the basis for constructing the coarse space.The construction first establishes trivial intersection with V_hf and then proves the direct-sum decomposition.Source: §9.2.2 · p. 61, §9.2 · p. 62

9.2 Basic approach

  • If V = V_hf ⊕ W_c, applying a suitable operator S to a basis of W_c produces linearly independent coarse basis functions and V = V_hf ⊕ V_c.The sufficient conditions include S being invertible or having the form I − Q_hf; examples include smoothed aggregation and classical AMG interpolation.Source: §9.2 · p. 63

9.3. Two basic coarsening algorithms

  • AMG coarsening selects coarse variables from vertices or vertex subsets in adjacency or strength graphs, chiefly through maximal independent sets or connected-subgraph aggregation.These two families define the basic algebraic alternatives for choosing coarse-grid degrees of freedom.Source: §9.2 · p. 63, §9.3 · p. 63

9.3.1. A maximal independent set (MIS) algorithm

  • The greedy MIS algorithm adds an unvisited vertex whose neighbors are unvisited, marks its neighborhood, and can recover geometric coarsening under a suitable vertex order.The correspondence holds when coarse vertices are visited first and the relevant connections are strong.Source: §9.3.1 · p. 64

9.3.2. An aggregation algorithm

  • Greedy aggregation partitions the strength graph into disjoint connected subgraphs, assigns uncovered vertices to neighboring aggregates, and can be recursively applied to form a multilevel hierarchy.The basic algorithm starts aggregates from unvisited vertices and their neighbors, then ensures every vertex belongs to a subset.Source: §9.3.2 · pp. 64–65

9.3.3. Aggressive coarsening

  • Aggressive coarsening replaces the strength graph by a graph encoding strong connections along paths, then applies MIS or aggregation to select vertices separated by larger graph distances.For path length l, the construction uses the adjacency graph of S^l and can be implemented recursively or directly on that graph.Source: §9.3.3 · p. 65, §9.4 · p. 66

9.4. Adaptive coarsening for classical AMG

  • Adaptive coarsening uses smoother behavior on the algebraic high-frequency space to enlarge the coarse set until the smoother norm falls below a threshold.Compatible relaxation adds coarse variables when ρ_k,f > δ_f, using filtered candidates or modified strength parameters when the initial coarse set is inadequate.Source: §9.4 · pp. 66–67

9.5. AGMG coarsening: a pairwise aggregation

  • AGMG greedily forms pairwise aggregates using strength, recursively merges pairs into larger aggregates, and targets bounded local Poincaré constants to control AMG convergence.The resulting aggregates produce unsmoothed, piecewise-constant prolongation with orthogonal columns.Source: §9.5 · pp. 67–68

9.6. Bibliographical notes

  • MIS-based coarse-grid selection includes graph connectivity and distance refinements, parallel randomized variants, and coupled or decoupled schemes (Ruge and St¨uben 1987; Trottenberg et al. 2001, Appendix A; Luby 1986; Cleary, Falgout, Henson and Jones 1998; Sterck et al. 2006; Yang 2006; Henson and Yang 2002).Source: §9.6 · p. 68
  • Aggregation coarsening draws on earlier aggregation methods and includes greedy aggregation, matching-based schemes, and algorithms such as AGMG (Vakhutinsky, Dudkin and Ryvkin 1979; Blaheta 1986; Marek 1991; Vanˇek et al. 1996b; Karypis and Kumar 1998; Napov and Notay 2012; Notay 2012).Source: §9.6 · p. 68
  • Specialized matching techniques optimize matrix invariants (D’Ambra and Vassilevski 2014, D’Ambra and Vassilevski 2013).Source: §9.6 · p. 69
  • Compatible Relaxation uses strength of connection to initialize coarse variables and the smoother to select additional ones (Brandt 2000a; Livne 2004; Falgout and Vassilevski 2004; Brannick and Falgout 2010).Source: §9.6 · p. 69
  • Other coarse-fine partitioning algorithms examine classical and compatible-relaxation perspectives.Source: §9.6 · p. 69
  • Adaptive aggregation methods group vertices using local measures of two-level convergence.Source: §9.6 · p. 69

10. GMG, AMG and a geometry-based AMG

This section examines the relationship between geometric and algebraic multigrid, developing geometry-based AMG through finite-element grids, prolongation operators, matrix graphs, and spectral AMGe. It also surveys foundational and element-based approaches, including BoxMG and AMGe variants for finite element problems.

10.1. Geometric multigrid method

  • GMG builds nested finite-element spaces on successively refined uniform grids and applies recursive V-cycles with interlevel inclusion operators and smoothers.The construction begins with a one-dimensional uniform partition, continuous piecewise-linear finite elements, multiple grids, and levelwise smoothers such as Gauss-Seidel.Source: §10.1 · pp. 69–70

Algebraic setting

  • GMG depends algebraically on the finest-grid stiffness matrix, prolongation matrices, and level smoothers, with coarse matrices formed by Galerkin products.Finite-element basis functions identify each space with a Euclidean vector space, enabling the operator formulation to become a hierarchy of matrix equations.Source: Algebraic setting · p. 71, §10.2 · pp. 72–73

10.2. Obtaining AMG from GMG

  • AMG can recover a Laplace GMG hierarchy from stiffness-matrix algebra and graph information because prolongation depends on graph topology rather than geometric coordinates.The construction forms the stiffness-matrix adjacency graph and coarsens it; the graph is closely related to the underlying grid graph, although discretizations can produce denser adjacency graphs.Source: §10.2 · p. 73

10.3 Obtaining GMG from AMG

  • The unified theory obtains GMG from AMG by using overlapping subdomain spaces, local operators, diagonal norms, interpolation operators, and coarse spaces assembled globally.The local decomposition and interpolation framework supplies the operators required by the abstract theory, with constants depending on subdomain overlap.Source: §10.3 · pp. 74–75

10.4. Spectral AMGe: a geometry-based AMG

  • Spectral AMGe selects each local coarse space from eigenvectors associated with its smallest eigenvalues, and its two-level convergence depends on the minimum retained local spectral threshold.For the geometric construction, constant local functions yield a global coarse space identical to the coarse finite-element space; a Poincaré inequality then implies uniform convergence.Source: §10.4 · pp. 76–77

10.5. Bibliographical notes

  • Foundational geometric and multigrid methods emerged through the works of Fedorenko, Bahvalov, Southwell, Brandt, and Hackbusch, alongside major advances in convergence analysis.The cited developments span pioneering geometric multigrid ideas, the first truly multigrid description, later multilevel methods, and analyses by Nicolaides, Bank and Dupont, Braess and Hackbusch, Bramble and collaborators, and Xu.Source: §10.5 · p. 78
  • BoxMG combines geometrically refined grids with algebraically defined interpolation, with reported results establishing its equivalence to Classical AMG.Details are referenced to Dendy and de Zeeuw, while equivalence results are attributed to MacLachlan, Moulton and Chartier.Source: §10.5 · p. 78
  • Element-based AMG methods assume an underlying grid and use element stiffness matrices to define interpolation, including plain, element-free, spectral, and spectral agglomerate AMGe.These approaches are developed to improve AMG robustness for finite element problems, with discussions of their variants referenced to Jones and Vassilevski, Brezina et al., Henson and Vassilevski, and Brezina et al.Source: §10.5 · p. 78

11. Energy-min AMG

This section develops energy-minimization AMG as a constrained approach to constructing coarse spaces, including locally discrete A-harmonic bases, and analyzes its two-level convergence. It relates the convergence behavior to subdomain size and overlap, including reported uniform convergence for practical and rough-coefficient problems.

11.1. Energy-minimization versus trace-minimization

  • Energy minimization is connected to trace minimization through constrained characterizations of the optimal coarse space and equivalent spectral formulations.The section introduces constraint sets and relates energy-minimizing prolongations to the optimal coarse space associated with the smoother-dependent operator.Source: §11.1 · pp. 79–80

11.2. Energy minimization basis for AMG and Schwarz methods

  • The AMG basis is obtained as the unique minimizer of total energy under local-support and normalization constraints, equivalently minimizing trace(Y^T A Y).The resulting optimization is described as well conditioned and efficiently solvable despite being global.Source: §11.2 · pp. 80–83
  • The globally energy-minimizing basis induces a non-overlapping partition into coarse elements and is discrete A-harmonic on each coarse element.The local harmonic property emerges as a by-product of the global construction rather than being imposed through local element boundaries.Source: §11.2 · pp. 84–85, §11.3 · p. 86

11.3. Convergence of energy minimization AMG

  • The section begins proving two-level convergence for energy-minimization AMG using overlapping subdomain spaces, cutoff operators, and minimization-defined coarse basis functions.The analysis introduces overlap-dependent constants and diagonal operators represented by the diagonal of A.Source: §11.3 · pp. 86–87
  • Theorem 11.9 bounds the two-level energy-minimization AMG convergence rate by a parameter 0 < µ < 1 depending only on subdomain sizes and overlaps.The construction uses local constant-function coarse spaces and subdomains satisfying a Poincaré inequality.Source: §11.3 · pp. 87–88

11.4. Bibliographical notes

  • Energy minimization unifies approximate solution strategies in Classical AMG and smoothed aggregation, while local finite-element energy minimization yields uniform two-level convergence.The literature also studies sparsity patterns, anisotropic problems, and constrained minimization preserving multiple vectors.Source: §11.4 · pp. 88–89
  • Numerical experiments report uniformly convergent two-grid and multigrid methods from energy-minimizing bases for many practical problems, especially those with rough coefficients (Wan et al. 1999/00, Wan 1998, Mandel et al. 1999, Xu and Zikatanov 2004).These methods also provide a framework for numerical homogenization and relate to homogenization methods in (Grauschopf, Griebel and Regler 1997) and M3 techniques in (Lipnikov, Moulton and Svyatskiy 2011).Source: §11.4 · p. 88

12. Classical AMG

This section presents classical AMG within an abstract framework, focusing on C/F splittings, prolongation, and the construction of local and global coarse spaces. It connects ideal and practical interpolation through energy minimization and examines two-level convergence, while noting the method’s historical development and limited multilevel theory.

12.1. Coarse spaces in classical AMG

  • Classical AMG defines coarse spaces through prolongation matrices after splitting graph vertices into disjoint coarse and fine sets, with C chosen as a maximal independent set under strength connections.A greedy C/F-splitting algorithm provides one construction of the coarse set.Source: §12.1 · p. 89
  • For fixed coarse indices, ideal interpolation Popt spans the coarse space and minimizes trace(P^TAP) over admissible prolongations, equivalently solving the interpolation equations; when A1 = 0, it also solves the constrained minimization problem.The corresponding coarse-grid matrix has minimal trace, and the minimizer satisfies W1_nc = 1_nF.Source: §12.1 · pp. 90–91

12.2. Quasi-optimality of ideal interpolation

  • The two-level method using ideal interpolation converges with ||E||_A ≤ 1 − δ, where δ depends only on graph maximum degree and the strong-connection threshold θ.Ideal interpolation is generally impractical because it can be dense, so practical AMG methods use sparse approximations motivated by energy minimization.Source: §12.2 · p. 92

12.3 Construction of prolongation matrix P

  • Classical direct, standard, and multipass interpolation approximate the ideal interpolation equations using Jacobi-based updates, rescaling, smoothing, or staged treatment of F-point subsets.Standard interpolation smooths direct interpolation before rescaling, while multipass interpolation proceeds across distance-based F-point subsets under aggressive coarsening.Source: §12.3.1 · p. 93, §12.3 · p. 94

12.3.2. Interpolation preserving a given vector

  • αAMG generalizes classical interpolation by constructing a prolongation that preserves a prescribed near-null vector, which need not be constant, then applying one Jacobi iteration to the interpolation problem.This extends constant-vector preservation used by direct and standard interpolation for scalar elliptic operators.Source: §12.3.2 · p. 95, §12.4 · p. 96

12.4 Classical AMG within the abstract AMG framework

  • Within the abstract AMG framework, classical AMG uses an M-matrix relative, strength-based MIS coarsening, and local subdomain decompositions whose weighted local operators are symmetric positive semidefinite.The construction verifies the assumptions needed to estimate convergence through the abstract theory.Source: §12.4 · pp. 96–97

12.4. Classical AMG within the abstract AMG framework

  • Classical AMG constructs local coarse spaces from restricted diagonal blocks and combines them into a global coarse space through the abstract framework.The construction selects local spaces and then obtains the global coarse space from them.Source: §12.4 · pp. 97–98
  • The two-level convergence rate depends on the minimum over local spaces of the second eigenvalue, min_j(λ^(2)_j).Source: §12.4 · p. 98
  • Under a discrete Poincaré inequality on each local space, the resulting two-level classical AMG method converges uniformly.The condition requires a constant c_j for each local space.Source: §12.4 · p. 98

12.5. Bibliographical notes

  • Classical AMG originated with Brandt et al. (1982b) and was improved by Stüben (1983), Brandt et al. (1985), and Ruge and Stüben (1987), with direct, standard, and multipass prolongations later surveyed.Uniformly bounded interpolation error is emphasized as crucial, while ideal interpolation minimizes an upper bound for the convergence rate.Source: §12.5 · pp. 98–99
  • Although classical AMG is highly successful in practice, solid theoretical justification remains limited beyond two-level methods, and two-level uniform convergence need not extend to multilevel schemes.This issue arises even when the two-level method uses an exact coarse-grid solver.Source: §12.5 · p. 98

13. Aggregation-based AMG

Aggregation-based AMG partitions graph vertices into connected, non-overlapping aggregates and constructs coarse spaces by extending vectors locally over those aggregates. Unsmoothed aggregation preserves one or multiple kernel or near-kernel vectors, while smoothing improves basis functions at the cost of denser coarse operators and more expensive setup.

13. Aggregation-based AMG

  • Aggregation partitions the filtered-matrix graph into non-overlapping subsets, each forming a connected subgraph; for finite elements, this corresponds to a non-overlapping decomposition of the domain.The aggregate sets contain the indices associated with vertices in the corresponding subdomains.Source: §13 · p. 99

13.1. Unsmoothed aggregation: preserving 1 kernel vector

  • Unsmoothed aggregation constructs prolongation columns by trivially extending the constant vector on each aggregate, yielding a coarse space spanned by those aggregate-based vectors.The resulting procedure is the unsmoothed aggregation AMG method.Source: §13.1 · p. 99, §13.3 · p. 101

13.2 Unsmoothed aggregation: preserving multiple vectors

  • The two-level convergence rate of unsmoothed aggregation depends only on the local Poincaré constants, under the framework’s verified assumptions.The construction and analysis use local matrices and diagonal restrictions defined analogously to classical AMG.Source: §13.2 · p. 100
  • Unsmoothed aggregation extends naturally to multiple kernel or near-kernel vectors, including the three rigid-body modes of two-dimensional elasticity, by constructing local aggregate basis vectors.For m linearly independent kernel vectors, the prolongation is constructed to reproduce each vector from corresponding coarse-grid components.Source: §13.2 · pp. 100–101

13.3 Smoothed aggregation

  • Smoothed aggregation applies a smoother, typically scaled Jacobi, to tentative basis functions while preserving kernel vectors; larger smoothing steps produce denser coarse operators and costlier setup.The smoothed coarse-grid graph is denser than the unsmoothed graph.Source: §13.3 · p. 102, Figure 13.13 · p. 102

13.4. Bibliographical notes

  • Aggregation-based methods include pairwise matching, nonlinear multilevel acceleration, and smoothed aggregation; the latter’s theory relies on sparsity and coarse-to-fine dimension assumptions that are difficult to verify generally.Smoothed aggregation was developed by Míka and Vaněk and later extended by Vaněk, Mandel, and Brezina.Source: §13.4 · p. 103

14. Problems with discontinuous and anisotropic coefficients

This section explains how classical AMG uses strength of connections to detect and resolve discontinuous jumps and anisotropy, yielding uniform two-level convergence under the stated assumptions. For jump coefficients, strong-connection components organize the coarse space, while for anisotropy, strength-based coarsening produces semi-coarsening and convergence independent of anisotropy and mesh parameters.

14. Problems with discontinuous and anisotropic coefficients

  • AMG methods should automatically resolve coefficient jumps and anisotropy, and classical AMG and SA-AMG are reported as robust through strength-of-connection techniques.The section studies model problems with discontinuous and anisotropic coefficients to explain this robustness.Source: §14 · p. 104

14.1. Jump coefficients

  • For jump coefficients, classical AMG defines prolongation using only strong connections, so the coarse space is the union of coarse spaces from strongly connected components.This construction is the same for A and its M-matrix relative A+ because only entries from A+ determine the coarse space.Source: §14.1 · pp. 104, 106
  • With sufficiently small ϵ, strength removes edges crossing between coefficient regions, producing a block-lower-triangular strength matrix with at least two blocks, even for disconnected or cross-point configurations.The resulting graph structure separates the interior of Ωϵ from the remaining vertices and can split Ωϵ into multiple components.Source: §14.1 · p. 104

14.1 Jump coefficients

  • The classical AMG two-level method with standard interpolation converges uniformly for the jump-coefficient problem.The proof uses a discrete Poincaré inequality on connected graphs and spectral equivalence between local operators and scaled graph Laplacians; the same result extends to direct interpolation with a slight modification.Source: §14.1 · pp. 106–107

14.2. Anisotropic problem

  • The resulting two-level classical AMG method converges uniformly for the anisotropic problem, with convergence rate independent of ε and mesh size h.The proof obtains a local spectral quantity equal to 1 and applies the general two-level convergence theorem.Source: §14.2 · pp. 108, 110
  • For strong anisotropy, standard coarsening with point relaxation fails to achieve uniform convergence, whereas strength-based coarsening yields semi-coarsening in the weakly coupled direction.For the model −u_xx − εu_yy = f, the strength graph coarsens only in one direction when 0 < ε ≪ 1.Source: §14.2 · pp. 108–109

14.3. Bibliographical notes

  • The bibliographical notes place these results within longstanding work on robust solvers for heterogeneous and anisotropic coefficients, including classical AMG, smoothed aggregation, geometric multigrid, and anisotropic AMG coarsening.They cite prior theoretical and numerical studies on coefficient jumps, matrix-dependent prolongation, and convergence of AMG methods.Source: §14.3 · pp. 110–111

15. Bootstrap and adaptive AMG

Bootstrap and adaptive AMG methods construct and repeatedly improve coarse spaces without assuming near-null spaces in advance, targeting problems where standard AMG variants converge slowly. A unified adaptive framework builds prolongations from test vectors and stops when the resulting V-cycle reaches the desired convergence rate.

15. Bootstrap and adaptive AMG

  • Bootstrap and adaptive AMG remove the need to know near-null spaces beforehand and self-improve coarse spaces until achieving the desired convergence rate on harder problems.The framework targets cases where standard Classical AMG or Smoothed Aggregation may converge slowly.Source: §15 · p. 111

15.1. Sparsity of prolongation matrices

  • Energy-minimizing prolongation permits prescribed or changing sparsity patterns, while least-squares and aggregation constructions provide mechanisms for fitting test vectors with sparsity control.Least-squares prolongation expands each row’s pattern using algebraically nearby coarse variables when the fitting error remains too large; aggregation optionally smooths the prolongator.Source: §15.1 · p. 111, §15.2 · p. 112

15.2. Notation

  • The generic adaptive framework represents a multilevel hierarchy through prolongation matrices and adjusts it so test vectors are approximated by the corresponding coarse-space ranges.The adaptive procedure changes the prolongations and hierarchy, then evaluates the resulting V-cycle convergence before further updates.Source: §15.2 · p. 113

15.3. A basic adaptive algorithm

  • The basic adaptive algorithm initializes random test vectors, coarsens the space, constructs prolongation by least squares or aggregation, and iteratively modifies test vectors and spaces until convergence meets δ0.Bootstrap AMG and adaptive SA use different procedures for updating the test-vector set after an unsuccessful convergence test.Source: §15.3 · pp. 113–114

15.4. Bibliographical notes

  • Although adaptive and bootstrap methods have succeeded in several settings, their added robustness carries significant cost and can fail to improve convergence if self-improvement is poorly implemented.In that failure mode, the method can degenerate to classical Krylov iteration preconditioned only by the multigrid smoother.Source: §15.4 · p. 115

16. Concluding remarks

The paper presents a coherent but incomplete theoretical framework for AMG methods, while identifying important algorithms and design directions that remain insufficiently understood. It also notes that several AMG software packages are in current use.

Scope and limitations

  • The presentation covers AMG algorithms that fit the paper’s theoretical frameworks, but excludes bootstrap and adaptive AMG, which lack a good theoretical understanding despite extending the framework to wider applications.The authors explicitly characterize the treatment as limited by current theoretical understanding and not complete.Source: §16 · p. 117

Open theoretical questions

  • Further analysis is needed for adaptive filtering, multilevel ILU, multilevel convergence in SA-AMG, BAMG, Adaptive AMG, and other methods that resist the proposed frameworks or remain theoretically unclear.Source: §16 · p. 117

Future method design

  • Most studied AMG methods optimize coarse-space choice for a given smoother, but future work could instead optimize the smoother, or jointly optimize coarsening and smoothing.Source: §16 · p. 117

Software

  • Several AMG software packages are currently in use, notably Hypre and Trilinos.Source: §16 · p. 117

Related papers

Loading 1611.01917v2…