PaperlayerView exact revision on arXiv

Source-linked AI summary

Algebraic Multigrid Methods

Jinchao Xu, Ludmil T Zikatanov

arXiv:1611.01917v2math.NA

TL;DR

The paper addresses the limited theoretical understanding of why diverse AMG methods work and how to choose effective coarse spaces. It develops a unified framework centered on smoothers, spectral optimality, and trace or energy minimization. The framework yields quasi-optimal coarse-space constructions and supports uniform two-level convergence under appropriate assumptions, while excluding bootstrap and adaptive AMG from its main theory.

  • Problem

    AMG methods combine theoretical and heuristic ideas, but a coherent theoretical account of their design and effectiveness remains limited.

  • Method

    The paper unifies AMG analysis around a fixed smoother, optimal low-frequency coarse spaces, trace minimization, energy minimization, graph coarsening, and related AMG constructions.

  • Results

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

  • Takeaways & Limitations

    Classical, energy-minimization, aggregation-based, geometric, and geometry-based AMG methods can be analyzed within a common framework as exact or approximate coarse-space constructions.

  • Takeaways & Limitations

    The framework is not complete: bootstrap and adaptive AMG are excluded because they still lack a good theoretical understanding.

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

The paper develops a coherent theoretical framework for AMG, addressing limited understanding of why existing methods work and how to design coarse spaces. It relates AMG to geometric multigrid and organizes several construction strategies within this framework.

  • Motivation: AMG addresses geometric multigrid’s reliance on readily available hierarchies of geometric grids by targeting systems with potentially unstructured discretizations.AMG generalizes geometric multigrid using algebraic information associated with the system and its discretization.
  • Motivation: The paper investigates AMG design and analysis theoretically, developing tools to unify results that had been distributed across theoretical and heuristic approaches.The authors re-examine existing results to provide a coherent theoretical description.
  • Coarse-space theory: For a fixed smoother, the two-level optimal coarse space is the low-end eigenspace of an operator such as RA, while practical AMG seeks inexpensive quasi-optimal approximations.The paper identifies this spectral space as theoretically optimal but too expensive to compute directly.
  • Coarse-space theory: The paper characterizes optimal coarse spaces through trace minimization and interprets the result as energy minimization for locally supported coarse basis functions.Energy-minimization AMG follows from this characterization, while classical and aggregation-based AMG are viewed as approximations.
  • AMG construction: AMG coarsening uses strength of connections to filter weak matrix entries and then coarsens the resulting adjacency graph using strategies such as maximal independent sets or aggregation.The coarsened graph is intended to preserve a good approximation of algebraically low-frequency components.
  • Scope and methods: The framework covers geometric multigrid, classical AMG, energy-minimization AMG, aggregation-based AMG, and geometry-based AMGe, while bootstrap and adaptive AMG remain outside its theoretical scope.Aggregation-based AMG is noted for preserving multidimensional near-null spaces, and classical AMG is analyzed for discontinuous coefficients and anisotropy.

3. Linear vector spaces and duals

This section establishes the finite-dimensional vector-space and dual-space notation used to formulate operators, matrices, inner products, and eigenvalue problems for AMG. It distinguishes stiffness and mass representations and emphasizes that operator spectra require careful interpretation.

  • Spaces and duals: The paper identifies a finite-dimensional space V with its dual V′ through an inner product for exposition, while retaining their distinct mathematical roles.This identification is used throughout the paper, but the authors note that it is not applied to infinite-dimensional spaces.
  • Bases and representations: Dual bases are needed to represent operators between a space and its dual, but they are used only for theoretical derivations rather than algorithm implementations.For finite element spaces, dual basis functions are generally globally supported and differ from nodal basis functions.
  • Bases and representations: An inclusion operator from a coarse subspace Vc into V has matrix representation P, while its dual operator has representation P^T with respect to the corresponding dual bases.The columns of P express coarse basis functions as combinations of fine-space basis functions.
  • Operator matrices: Using the same basis for domain and range yields one matrix representation of A, whereas using a primal basis for the domain and a dual basis for the range yields the stiffness matrix representation.The associated matrix converting between these representations is the mass matrix.
  • Eigenvalues and eigenvectors: For finite element operators, the matrix spectrum depends on the chosen representation and identification, so eigenvalues of A must be defined with care.The operator A maps between V and V′ even when those spaces are identified for convenience; related operators such as RA can have clearer spectral interpretations.
  • Motivation: Clarifying the distinctions among spaces, duals, bases, and operator representations is necessary for the subsequent presentation of algebraic multigrid methods.The section presents these foundations to avoid ambiguity in later AMG analysis.

4. Basic iterative methods

This section formulates Jacobi, Gauss-Seidel, and subspace-correction iterations in an abstract operator framework. It relates convergence to positivity and decomposition properties, including extensions to symmetric semidefinite and anisotropic problems.

  • General iterative methods: A linear iterative method updates the current approximation using an operator B applied to the residual, with B acting as an approximate inverse of A.The general iteration is u_m = u_{m−1} + B(f − Au_{m−1}).
  • General iterative methods: A nonsymmetric iteration can be symmetrized by applying B followed by its adjoint B′, producing an equivalent iteration with operator B̄.The symmetrized operator is used to analyze convergence through positivity conditions.
  • Convergence: Convergence of the symmetrized iteration is equivalent to positivity of B̄, and this is further characterized by positivity of G = (B′)^−1 + B^−1 − A.The equivalence connects iteration convergence with an operator inequality useful in subsequent analysis.
  • Jacobi and Gauss-Seidel: Modified Jacobi and Gauss-Seidel methods fit the general iteration framework, with convergence conditions determined by their choices of diagonal, triangular, and relaxation operators.The paper assumes a suitable Jacobi relaxation parameter and uses ω = 1 for Gauss-Seidel.
  • Subspace corrections: Parallel and successive subspace correction methods generalize relaxation by decomposing the space into auxiliary subspaces and applying local correction operators.The auxiliary spaces need not be subspaces of V, but each is connected to V by a linear operator.
  • Subspace corrections: Under SPD local solvers and suitable space-decomposition assumptions, subspace-correction theory supplies identities and bounds for the resulting iterative operators.The framework assumes energy inner products on auxiliary spaces and approximate inverses for the restricted operators.
  • Generality: The estimates remain valid for anisotropic and jump-coefficient problems, with constants depending on overlap topology rather than those coefficient or anisotropy properties.The presentation also extends the SPD results to symmetric semipositive definite systems under additional assumptions.

5. Abstract multigrid methods and 2-level theory

The paper formulates AMG abstractly around a smoother and coarse space, develops two-level convergence theory, and characterizes optimal and quasi-optimal coarse spaces. It also explains algebraic frequencies and emphasizes that rigorous uniform multilevel theory remains difficult.

  • Abstract multigrid methods and 2-level theory: AMG can be treated as Abstract Multi-Grid, with two-level methods extended recursively to multilevel V-cycles, although multilevel convergence theory is substantially harder.The paper focuses mainly on two-level convergence theory.
  • Abstract multigrid methods and 2-level theory: A two-level AMG method combines a smoother, a coarse space linked through prolongation P, and a coarse-space solver Bc.The algorithm applies coarse-grid correction followed by post-smoothing.
  • Abstract multigrid methods and 2-level theory: The design problem balances the smoother R and coarse space Vc, typically fixing Jacobi or Gauss-Seidel before optimizing Vc.The framework assumes an SPD matrix associated with the smoother, while also treating SSPD problems and possible kernels.
  • Optimal coarse spaces: For a fixed smoother, the optimal coarse space is formed from eigenvectors associated with the lower end of the spectrum of an operator such as RA.The two-level convergence rate is minimized by the corresponding spectral coarse space.
  • Quasi-optimality and algebraic frequencies: Two-level AMG is uniformly convergent when the relevant coarse-space approximation quantity remains uniformly bounded, whereas rigorous uniform multilevel results without geometric information remain widely open.Algebraic low-frequency eigenfunctions may be highly oscillatory geometrically, so algebraic and geometric frequency notions need not coincide.

6. A general approach to the construction of coarse space

The section introduces an abstract framework for constructing AMG coarse spaces through space decompositions and subspace corrections.

  • The framework constructs coarse spaces using space decomposition and subspace corrections.
  • Technical lemmas are introduced as analytic tools for the subsequent construction and analysis.

1. For all v

The construction uses auxiliary spaces, local operators, projections, and assumptions that support global coarse-space analysis.

  • A fictitious-space lemma provides an analytic basis for the coarse-space construction under stated conditions on the transfer operator.
  • Auxiliary spaces need not be subspaces of the original space but are connected to it by linear operators.
  • The original space is represented as a sum of subspaces, with local operators assumed symmetric and positive semi-definite.
  • Each local space is equipped with a symmetric positive definite operator used in defining the decomposition and associated projections.
  • The analysis imposes stability, decomposition, and neighborhood-inclusion assumptions involving constants Cp,1, Cp,2, and local neighborhoods N(A_j).
  • The global coarse space is defined from the local construction and embedded naturally into the original space.

6 A GENERAL APPROACH TO THE CONSTRUCTION OF COARSE SPACE

The framework defines product-space operators and an additive preconditioner, then derives two-level error and convergence bounds under explicit assumptions.

  • Product spaces combine the coarse space with local spaces, and the natural inclusion embeds the coarse component into the original space.
  • An additive preconditioner is introduced on the product space to support the abstract convergence analysis.
  • Under the assumptions, every vector admits a decomposition satisfying the required error estimate, with constants depending on coarse-space and local stability parameters.
  • The lemmas establish the two inequalities needed to control the decomposition and preconditioner under the stated assumptions.
  • The resulting two-level AMG method converges at a rate bounded using µc, Cp,1, Cp,2, and cD.
  • The framework is presented as applicable to classical AMG, smoothed aggregation AMG, spectral AMGe, and related algorithms, while multilevel results remain difficult in general algebraic settings.

7. Graphs and sparse matrices

This section defines graph concepts for sparse symmetric matrices and explains how M-matrix relatives support AMG construction and analysis.

  • Graph theory: Graphs consist of vertices and unordered edges, with adjacency, paths, connectivity, subgraphs, neighborhoods, degree, distance, diameter, and independent sets defined explicitly.
  • Sparse matrices: The adjacency graph of a symmetric matrix represents nonzero couplings, and matrix irreducibility is equivalent to graph connectivity.
  • Sparse matrices: Sparse matrices generally encode combinatorial and topological graph properties but do not provide geometric information about vertex placement.
  • M-matrix relatives: AMG algorithms commonly filter a positive-semidefinite matrix to construct an M-matrix used for hierarchy components and coarse-space design.
  • M-matrix relatives: The M-matrix-relative approach supports estimates for coarse spaces, but its construction and guarantees depend on problem assumptions such as coefficient alignment, connectivity, and null-space structure.
  • M-matrix relatives: For finite-element matrices, an M-matrix relative can be spectrally equivalent to the original matrix, with constants depending only on mesh shape regularity, while its graph is connected.

8. Strength of connections

Strength of connection identifies graph relationships that should be retained when constructing AMG coarse spaces. The paper contrasts heuristic and theory-based definitions, while noting symmetry and sparsity trade-offs.

  • AMG coarsening retains graph relationships where algebraically smooth vectors vary slowly, using strength of connection to identify such pairs.Strongly connected vertices can be aggregated or represented by one retained degree of freedom.
  • Classical AMG filters weak edges, then coarsens the filtered graph using maximal independent sets or aggregation.The strength matrix is Boolean, with entries determined by the selected strength criterion.
  • For an M-matrix, larger |aij| corresponds to smaller (ui − uj)^2 and slower variation of algebraically smooth error.This observation motivates coefficient-based strength functions.
  • Strength functions may be nonsymmetric, but the theoretical framework uses the symmetrized smoother and therefore considers symmetric strength functions.The original definition can make j strongly connected to i without the reverse relation.
  • Choosing prolongation sparsity balances approximation quality against computational cost: denser P improves coarse approximation, whereas sparser P is cheaper.The paper also notes that classical AMG strength definition (8.7) ignores non-negative stiffness-matrix entries.
  • The paper presents classical, lean, local-optimization, aggregation-based, and Cauchy-Schwarz-based strength definitions.The aggregation-based construction uses local generalized eigenvectors, while Lean AMG uses relaxed test vectors and affinity.

9. Coarsening strategies

AMG coarsening constructs coarse spaces that approximate algebraically smooth error components without relying on a geometric hierarchy. It uses graph filtering, vertex selection or aggregation, and prolongation construction recursively.

  • The coarse space should approximate algebraically smooth error components for which the chosen smoother converges poorly.This is the central objective of the coarsened problem.
  • Unlike geometric multigrid, AMG reverse-engineers a hierarchy of spaces because no geometric refinement hierarchy is available.The construction can be organized through degrees of freedom and dual bases.
  • In the finite-element analogy, coarse-grid vertices correspond to selected degrees of freedom, and an MIS can recover geometric coarsening in suitable cases.For acute triangulations, the coarse vertices form a maximal independent set in the refined-mesh graph.
  • A general AMG coarsening cycle filters weak graph edges, selects coarse variables by MIS or aggregation, constructs a tentative space, smooths it, and forms Ac = P^TAP recursively.The same steps are repeated on successively coarser matrices.

1. Form the following two non-overlapping decompositions

The section develops coarse-space construction from selected coarse degrees of freedom, then distinguishes classical MIS coarsening from aggregation and aggressive coarsening strategies.

  • 9.2.2. Construction of Vc: A nonsingular Gram matrix ensures that the constructed pre-coarse space complements the high-frequency space.The resulting decomposition is V = Vhf ⊕ Wc.
  • 9.2 Basic approach: Applying a suitable operator S to a basis of Wc produces linearly independent coarse basis functions and a decomposition V = Vhf ⊕ Vc.The conditions include invertibility or projection-based constructions.
  • 9.2 Basic approach: Smoothed aggregation uses S = I − ωD^-1A, while classical AMG uses S = I − Qhf with ideal or approximate A-orthogonal projection.These are examples of postprocessing a tentative coarse space.
  • 9.3. Two basic coarsening algorithms: Classical AMG selects coarse degrees of freedom as a maximal independent set in the strength graph, whereas aggregation AMG partitions that graph into connected subgraphs.Both strategies identify coarse variables from graph structure.
  • 9.3.1. A maximal independent set (MIS) algorithm: The greedy MIS algorithm visits vertices, retains an unvisited vertex, marks it and its neighbors, and stops after all vertices are visited.With suitable ordering and strong connections, it can recover geometric coarsening.
  • 9.3.2. An aggregation algorithm: Greedy aggregation builds connected aggregates from a vertex and its neighbors, assigns uncovered vertices to neighboring aggregates, and can be applied recursively.This produces a multilevel hierarchy of aggregates.
  • 9.3.3. Aggressive coarsening: Aggressive coarsening forms a MIS on a graph encoding strong connections along paths, selecting coarse vertices separated by graph distance greater than l.It uses the adjacency graph of S^l instead of the original strength graph.

10. GMG, AMG and a geometry-based AMG

Geometric multigrid uses nested finite-element spaces and prolongation operators across refined grids. The paper argues that key geometric constructions can be recovered algebraically from stiffness-matrix and graph information.

  • The geometric multigrid model uses a one-dimensional uniform grid, piecewise-linear finite elements, and a nested sequence of refined spaces.Each level has nodal basis functions and an associated matrix representation.
  • A classic V-cycle applies smoothing and transfers between levels through inclusion or prolongation operators, recursively reducing the problem to coarser grids.The algebraic version uses matrices representing the same transitions.
  • Geometric multigrid depends primarily on the finest-grid stiffness matrix and the prolongation matrix at each level, with algebraic smoothers also required.Coarse stiffness matrices are formed recursively from prolongation operators.
  • For linear finite elements, prolongation depends on the grid’s natural graph rather than point coordinates, and that graph is close to the stiffness-matrix adjacency graph.This motivates algebraic recovery of geometric constructions.
  • For bilinear elements on a square, the stiffness matrix matches a scaled 9-point finite-difference stencil, whose adjacency graph includes mesh diagonals.The matrix graph is therefore denser than the mesh graph.
  • The prolongation matrix encodes the coefficients of coarse-grid basis functions in the fine-grid basis.Its stencil gives a compact representation of those coefficients.
  • The geometry-based AMG construction uses level spaces, operators, decompositions, and coarse spaces; under the stated estimate, the two-level geometric multigrid method converges uniformly.The result is conditional on the assumptions used in the estimate.

11. Energy-min AMG

This section develops energy-minimization coarse spaces for AMG through constrained trace minimization and its equivalent energy formulation. The resulting basis functions support quasi-optimal coarse spaces, local harmonic structure, and uniformly convergent two-level methods under stated assumptions.

  • Trace minimization: The optimal coarse space can be characterized by trace minimization over prolongation matrices satisfying stability and normalization constraints.The relevant spectral operator has the same spectrum as the symmetrized product involving A and the smoother.
  • Energy-minimization formulation: Energy-minimization AMG constructs coarse spaces by solving a constrained global optimization problem for locally supported coarse basis functions.The approach is motivated by the equivalence between the optimal coarse-space characterization and trace minimization.
  • Existence and uniqueness: The energy-minimizing basis problem has a unique solution and a convex objective with a convex constraint.The construction is therefore well posed as a global minimization problem.
  • Local harmonicity and coarse elements: Energy-minimizing basis functions are locally discrete A-harmonic, with coarse elements formed from intersections of basis-function supports.These intersections form a finite non-overlapping partition, although the coarse elements may have complicated shapes and need not be explicitly defined.
  • Convergence: The resulting energy-minimization AMG has a two-level convergence bound whose parameter depends only on the size and overlaps of the subdomains.Reported numerical experiments also show uniformly convergent two-grid and multigrid methods for many practical problems, especially with rough coefficients.

12. Classical AMG

Classical AMG defines coarse spaces through graph-based C/F coarsening and interpolation, then interprets ideal interpolation as a trace-minimizing construction within the abstract AMG framework. Its two-level convergence is uniform under stated assumptions, while practical methods use sparse approximations because ideal interpolation may be dense.

  • Coarsening: Classical AMG splits the matrix graph into disjoint coarse and fine sets, with C a maximal independent set based on strong connections.The partition satisfies C ∪ F = {1, ..., n} and C ∩ F = ∅.
  • Interpolation: Ideal interpolation constructs coarse basis functions by correcting tentative coarse functions with fine-space components.The resulting prolongation Popt is the basis matrix for the ideal coarse space.
  • Energy minimization: For fixed coarse indices, Popt minimizes the trace of the coarse-grid matrix over admissible prolongations.The theorem identifies the same minimizer through the trace-minimization problem and the corresponding interpolation equations.
  • Convergence: The two-level method with ideal interpolation converges at a rate bounded by 1 − δ, where δ depends only on graph degree and the strong-connection threshold.Uniform convergence follows under the framework’s assumptions, including the stated high-frequency characterization.
  • Practical construction: Ideal interpolation is generally impractical because its prolongation and coarse-grid matrix can be dense, motivating sparse approximations used by classical AMG and related methods.Classical AMG, energy-minimization, and smoothed aggregation methods approximate the relevant minimization over sparse matrices.
  • Interpolation: The prolongation preserves algebraically smooth errors by preserving a selected near-null vector, which need not be constant.This generalizes constant-vector preservation used for scalar elliptic operators.

13. Aggregation-based AMG

Aggregation-based AMG partitions graph vertices into connected, non-overlapping aggregates and uses their local basis functions to form a global coarse space. Unsmoothed aggregation is simple and extensible to multiple kernel vectors, while smoothing improves basis functions at the cost of denser coarse operators.

  • Aggregation construction: Aggregation partitions graph vertices into non-overlapping subsets, each forming a connected subgraph.For finite elements, the aggregates correspond to a non-overlapping decomposition of the domain.
  • Unsmoothed aggregation: Unsmoothed aggregation forms prolongation columns by trivially extending aggregate indicator vectors, so the coarse space is their span.The prolongation is P = (p1, ..., pJ), with pj = Πj1nj.
  • Analysis: The two-level analysis verifies the framework’s assumptions for aggregation using local matrices and restricted diagonals of A.The cited result applies the same local-operator argument used for classical AMG.
  • Multiple near-kernel vectors: Aggregation-based AMG can preserve multiple kernel or near-kernel vectors by constructing local prolongation columns from their restrictions to each aggregate.The construction extends from three vectors to an arbitrary m-dimensional kernel when m ≪ n.
  • Multiple near-kernel vectors: The method extends to elasticity by preserving three rigid-body-motion vectors through aggregate-local prolongation construction.The cited construction explicitly treats the two-dimensional elasticity case.
  • Smoothed aggregation: Smoothed aggregation applies a smoother to prolongation basis functions, producing smoother columns than unsmoothed aggregation.A scaled Jacobi smoother with RS = ωD^-1 is given as a typical choice, while kernel vectors remain preserved.
  • Smoothed aggregation: A larger smoothing step count may improve convergence but increases prolongation and coarse-matrix density, making setup more expensive.Figure 13.13 compares the sparser unsmoothed coarse graph with the denser smoothed one.

14. Problems with discontinuous and anisotropic coefficients

Classical AMG uses strength of connections to detect discontinuities and anisotropy, producing coarse spaces and coarsening patterns suited to heterogeneous problems. The resulting two-level methods are proved uniformly convergent for jump coefficients and anisotropic problems under the stated assumptions.

  • Jump coefficients: Strength of connections removes weak edges across coefficient jumps, yielding a block-lower-triangular graph with separate connected components.The first block corresponds to vertices interior to the low-coefficient region, while the second contains the remaining vertices.
  • Jump coefficients: For the illustrated jump problem, the strength graph disconnects the low-coefficient region from the rest and can split that region into two components linked through one point.The figures show these components for both structured and unstructured meshes.
  • Classical AMG coarsening: Classical AMG prolongation uses only strong connections, so its coarse space is the union of coarse spaces associated with strongly connected components.The construction gives the same coarse space for A and its M-matrix relative A+ because only entries from A+ define it.
  • Jump coefficients: Theorem 14.4 states that the classical AMG two-level method with the defined coarse space is uniformly convergent.The proof combines a discrete graph Poincaré inequality, local spectral equivalence, and a bounded coarse-space approximation quantity.
  • Anisotropic coefficients: For anisotropy, strength-based coarsening produces semi-coarsening, and the two-level convergence rate is independent of ε and the mesh size h.The result concerns the problem −u_xx − εu_yy = f on a uniform grid.

15. Bootstrap and adaptive AMG

Bootstrap and adaptive AMG methods address problems whose near-null spaces are not known in advance by iteratively constructing coarse spaces from test vectors. The framework updates coarsening, prolongation, and multilevel hierarchies until the current method meets a convergence criterion.

  • Motivation: Adaptive and bootstrap AMG target harder problems where standard classical or smoothed-aggregation variants may not provide suitable coarse spaces.Their central purpose is to eliminate the assumption that near-null spaces are known beforehand.
  • Prolongation construction: Least-squares prolongation fits test vectors under a prescribed sparsity pattern, while aggregation assigns vectors to aggregates and optionally smooths the resulting prolongator.The least-squares method can expand graph-based neighborhoods subject to a maximum number of row nonzeros.
  • Framework: The generic adaptive framework represents a hierarchy through prolongation matrices and constructs coarse spaces so test vectors are approximated by ranges of prolongation operators.The number of levels can be unknown during the adaptive procedure.
  • Adaptive procedure: The generic adaptive algorithm repeatedly coarsens, restricts test vectors, builds prolongation matrices, forms a V-cycle, and updates the hierarchy when its convergence measure exceeds δ0.Bootstrap AMG and adaptive SA use different procedures for updating test vectors and prolongations within this framework.
  • Caveat: Poor implementation of self-improving coarse spaces can reduce adaptive or bootstrap multigrid to a method with no better convergence properties than a Krylov method preconditioned by the smoother.The framework distinguishes the underlying multigrid algorithm from the additional adaptive elements.

16. Concluding remarks

The paper offers a coherent theoretical presentation of selected AMG methods but acknowledges that its coverage and understanding remain incomplete. It also identifies joint optimization of coarsening and smoothing as an open direction.

  • Scope and limitations: The presentation is limited to AMG algorithms that fit the paper’s theoretical frameworks, while bootstrap and adaptive AMG remain exceptions with limited theoretical understanding.These methods are included for their algorithmic value in extending other AMG approaches to wider applications.
  • Scope and limitations: Several literature algorithms remain outside the article because they cannot be readily cast within its frameworks or are not yet understood at a reasonable theoretical level.Examples include adaptive filtering, multilevel ILU methods, and multilevel convergence properties of smoothed aggregation AMG.
  • Open directions: The studied AMG methods optimize coarse spaces for a given smoother, leaving optimization of the smoother, or of both smoother and coarsening, for further investigation.The authors identify this as a subject worthy of further study.
Loading 1611.01917v2…