pith. sign in

arxiv: 2606.18404 · v1 · pith:GSEIV5IHnew · submitted 2026-06-16 · 🧮 math.NA · cs.NA

Two-level convergence of Algebraic Multigrid with Overlapping Smoothers and Spectral Coarse Grids

O. A. Krzysik , B. S. Southworth , H. Al Daas This is my paper

Pith reviewed 2026-06-26 23:14 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords algebraic multigridconvergence theoryoverlapping smoothersspectral coarse gridsdomain decompositionweak approximation propertyfinite element discretizations
0
0 comments X

The pith

The LS-AMG-DD solver's coarse space satisfies a weak approximation property whose constant is bounded by a user-controlled local spectral cutoff threshold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a two-level convergence theory for the least-squares algebraic multigrid domain-decomposition solver on sparse symmetric positive definite matrices that admit a Gram representation. It shows that coarse spaces built from local eigenproblems on nonoverlapping aggregates satisfy a weak approximation property measured in the norm induced by an aggregate-wise block-Jacobi smoother, and that this constant is controlled directly by the chosen spectral cutoff. The property is inserted into standard sharp bounds for multiplicative two-level cycles, producing an overall convergence estimate factored cleanly by the cutoff and a smoother norm-comparison constant. Explicit estimates for the comparison constant are supplied for block-Jacobi and overlapping additive Schwarz smoothers, together with a new additive-Schwarz bound controlled by a computable quantity no larger than the coloring constant. Numerical tests on H1, H(div), and H(curl) finite-element discretizations illustrate the predicted behavior.

Core claim

The solver's coarse space satisfies a weak approximation property in a norm induced by an aggregate-wise block-Jacobi smoother, and the corresponding approximation constant is bounded by a user-controlled local spectral cutoff threshold. When this property is combined with standard sharp theory for multiplicative two-level cycles, the resulting two-level bound factors cleanly into the cutoff threshold and a smoother norm-comparison constant; explicit bounds on the comparison constant are derived for block Jacobi and overlapping additive Schwarz smoothers, and a new convergence bound for additive Schwarz is given in terms of a trivially computable constant bounded above by the coloring consta

What carries the argument

Weak approximation property measured in the norm induced by an aggregate-wise block-Jacobi smoother, with constant bounded by the local spectral cutoff threshold.

If this is right

  • The two-level convergence bound factors explicitly into the spectral cutoff threshold and a smoother norm-comparison constant.
  • Explicit upper bounds on the norm-comparison constant hold for both block-Jacobi and overlapping additive Schwarz smoothers.
  • A new additive-Schwarz convergence bound depends only on a computable constant that is at most the coloring constant.
  • Numerical tests on scalar H1 and vector H(div), H(curl) problems confirm the predicted mesh-size and polynomial-degree independence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Choosing a smaller cutoff should produce a proportionally tighter convergence factor provided the smoother comparison constant remains moderate.
  • The coloring-constant bound on the additive-Schwarz term suggests the theory may apply to other overlapping decompositions whose overlap graph has bounded chromatic number.
  • If similar weak approximation properties can be shown for non-Gram matrices, the same factoring argument would yield convergence estimates without the Gram assumption.

Load-bearing premise

The matrices admit a Gram representation A equals G transpose G so that the solver construction and the direct application of standard multiplicative two-level cycle theory are valid once the weak approximation property is proved.

What would settle it

Compute the approximation constant in the block-Jacobi norm for a sequence of successively refined finite-element matrices; if the constant grows with refinement while remaining larger than the chosen cutoff, the claimed bound is false.

read the original abstract

We recently developed the least-squares algebraic-multigrid domain-decomposition (LS-AMG-DD) solver as an algebraic multilevel method for sparse symmetric positive definite matrices that admit a Gram representation \(A=G^{\top}G\) \cite{southworth2026lsamgdd}. Many problem classes admit such structure, including many conforming finite-element discretizations. The solver constructs coarse spaces from local eigenproblems on nonoverlapping, algebraic aggregates and uses Schwarz-type smoothers on the induced overlapping subdomains. This paper develops a novel two-level convergence theory for this solver. Our theory shows that the solver's coarse space satisfies a weak approximation property in a norm induced by an aggregate-wise block-Jacobi smoother, and moreover, that the corresponding approximation constant is bounded by a user-controlled local spectral cutoff threshold. We combine this approximation property with standard sharp theory for multiplicative two-level cycles. The resulting two-level bound is cleanly factored by the cutoff threshold and a smoother norm-comparison constant; we derive explicit bounds for this constant for block Jacobi and overlapping additive Schwarz smoothers. We also develop a new convergence bound for additive Schwarz methods in terms of a trivially computable constant that is bounded above by the coloring constant. Numerical experiments on scalar \(H^1\), vector \(H(\operatorname{div})\), and vector \(H(\operatorname{curl})\) finite-element problems provide supporting evidence for the theory, including evidence for the solver's insensitivity to mesh refinement and polynomial degree.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper develops a two-level convergence theory for the LS-AMG-DD algebraic multigrid solver applied to sparse SPD matrices admitting a Gram representation A = G^T G. It establishes that the spectral coarse space (constructed from local eigenproblems on nonoverlapping aggregates) satisfies a weak approximation property measured in the norm induced by an aggregate-wise block-Jacobi smoother, with the approximation constant bounded above by a user-controlled local spectral cutoff threshold. This property is then combined with standard sharp theory for multiplicative two-level cycles to produce a convergence-factor bound that factors cleanly into the cutoff threshold and a smoother norm-comparison constant; explicit bounds on the latter are derived for both block-Jacobi and overlapping additive Schwarz smoothers. A new convergence bound for additive Schwarz methods (controlled by a trivially computable constant bounded by the coloring constant) is also presented. Numerical experiments on scalar H^1, vector H(div), and vector H(curl) finite-element discretizations are included to illustrate the theory, particularly mesh- and polynomial-degree independence.

Significance. If the derivations hold, the work supplies a parameter-controlled convergence bound for an algebraic multilevel solver that applies to a broad class of finite-element problems (including high-order and vector-valued cases). The explicit derivation of the norm-comparison constants, the new additive-Schwarz bound, and the supporting numerical evidence for insensitivity to h and p are concrete strengths that would advance the analysis of overlapping Schwarz smoothers paired with spectral coarse spaces.

minor comments (2)
  1. The abstract invokes 'standard sharp theory for multiplicative two-level cycles' without a specific citation; adding the precise reference (e.g., the relevant theorem number from the cited literature) in the introduction or theory section would improve traceability.
  2. Notation for the block-Jacobi norm and the A-norm should be introduced with a short comparison table or explicit definition early in the theory section to make the norm-comparison step immediately legible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of the contributions, and the recommendation for minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity: new approximation property and explicit norm bounds derived independently; combined with external standard theory

full rationale

The paper's central derivation establishes a weak approximation property in the block-Jacobi-induced norm with bound controlled by the user-specified spectral cutoff threshold, then derives explicit bounds on the smoother norm-comparison constant for the cited smoothers. These steps are presented as novel contributions rather than reductions to fitted quantities or prior self-citations. The combination invokes 'standard sharp theory for multiplicative two-level cycles' from the literature (not overlapping-author citations that bear the load), and the Gram representation A = G^T G is an explicit modeling assumption on the input matrices rather than a constructed output. No self-definitional, fitted-prediction, or ansatz-smuggling patterns appear in the provided abstract or described chain; the result remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The theory rests on the existence of a Gram representation for the matrices and on background results from algebraic multigrid theory; no new free parameters are introduced beyond the user-controlled cutoff, and no new entities are postulated.

axioms (2)
  • domain assumption Matrices admit a Gram representation A = G^T G
    Stated in the abstract as the setting for which the solver and theory apply; invoked to justify the algebraic construction.
  • standard math Standard sharp theory for multiplicative two-level cycles applies once the weak approximation property holds
    Explicitly invoked when combining the new approximation result with existing cycle analysis.

pith-pipeline@v0.9.1-grok · 5810 in / 1611 out tokens · 28632 ms · 2026-06-26T23:14:02.235178+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 20 canonical work pages

  1. [1]

    Al Daas and L

    H. Al Daas and L. Grigori , A Class of Efficient Locally Constructed Preconditioners Based on Coarse Spaces , SIAM Journal on Matrix Analysis and Applications, 40 (2019), pp. 66--91, https://doi.org/10.1137/18M1194365

    work page doi:10.1137/18m1194365 2019

  2. [2]

    Al Daas , L

    H. Al Daas , L. Grigori, P. Jolivet, and P.-H. Tournier , A Multilevel Schwarz Preconditioner Based on a Hierarchy of Robust Coarse Spaces , SIAM Journal on Scientific Computing, 43 (2021), pp. A1907--A1928, https://doi.org/10.1137/19M1266964

    work page doi:10.1137/19m1266964 2021

  3. [3]

    Al Daas , P

    H. Al Daas , P. Jolivet, and T. Rees , Efficient algebraic two-level schwarz preconditioner for sparse matrices , SIAM Journal on Scientific Computing, 45 (2023), pp. A1199--A1213, https://doi.org/10.1137/22M1469833

    work page doi:10.1137/22m1469833 2023

  4. [4]

    Al Daas , P

    H. Al Daas , P. Jolivet, and J. A. Scott , A Robust Algebraic Domain Decomposition Preconditioner for Sparse Normal Equations , SIAM Journal on Scientific Computing, 44 (2022), pp. A1047--A1068, https://doi.org/10.1137/21M1434891

    work page doi:10.1137/21m1434891 2022

  5. [5]

    N. Bell, L. N. Olson, J. Schroder, and B. Southworth , Pyamg: algebraic multigrid solvers in python , Journal of Open Source Software, 8 (2023), p. 5495

    2023

  6. [6]

    Cai and M

    X.-C. Cai and M. Sarkis , A restricted additive schwarz preconditioner for general sparse linear systems , Siam journal on scientific computing, 21 (1999), pp. 792--797

    1999

  7. [7]

    Dolean, P

    V. Dolean, P. Jolivet, and F. Nataf , An Introduction to Domain Decomposition Methods , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2015

    2015

  8. [8]

    R. D. Falgout and P. S. Vassilevski , On generalizing the algebraic multigrid framework , SIAM Journal on Numerical Analysis, 42 (2004), pp. 1669--1693, https://doi.org/10.1137/S0036142903429742

    work page doi:10.1137/s0036142903429742 2004

  9. [9]

    R. D. Falgout, P. S. Vassilevski, and L. T. Zikatanov , On Two-Grid Convergence Estimates , Numerical Linear Algebra with Applications, 12 (2005), pp. 471--494, https://doi.org/10.1002/nla.437

    work page doi:10.1002/nla.437 2005

  10. [10]

    Galvis and Y

    J. Galvis and Y. Efendiev , Domain Decomposition Preconditioners for Multiscale Flows in High-Contrast Media: Reduced Dimension Coarse Spaces , Multiscale Modeling & Simulation, 8 (2010), pp. 1621--1644, https://doi.org/10.1137/100790112

    work page doi:10.1137/100790112 2010

  11. [11]

    D. A. Ham, P. H. J. Kelly, L. Mitchell, C. J. Cotter, R. C. Kirby, K. Sagiyama, N. Bouziani, S. Vorderwuelbecke, T. J. Gregory, J. Betteridge, D. R. Shapero, R. W. Nixon-Hill, C. J. Ward, P. E. Farrell, P. D. Brubeck, I. Marsden, T. H. Gibson, M. Homolya, T. Sun, A. T. T. McRae, F. Luporini, A. Gregory, M. Lange, S. W. Funke, F. Rathgeber, G.-T. Bercea, a...

    work page doi:10.25561/104839 2023

  12. [12]

    Heinlein, A

    A. Heinlein, A. Klawonn, J. Knepper, and O. Rheinbach , Adaptive GDSW Coarse Spaces for Overlapping Schwarz Methods in Three Dimensions , SIAM Journal on Scientific Computing, 41 (2019), pp. A3045--A3072, https://doi.org/10.1137/18M1220613

    work page doi:10.1137/18m1220613 2019

  13. [13]

    T. V. Kolev and P. S. Vassilevski , Parallel auxiliary space amg for H ( curl ) problems , Journal of Computational Mathematics, 27 (2009), pp. 604--623, https://doi.org/10.4208/jcm.2009.27.5.013

    work page doi:10.4208/jcm.2009.27.5.013 2009

  14. [14]

    T. V. Kolev and P. S. Vassilevski , Parallel auxiliary space amg solver for H ( div ) problems , SIAM Journal on Scientific Computing, 34 (2012), pp. A3079--A3098, https://doi.org/10.1137/110859361

    work page doi:10.1137/110859361 2012

  15. [15]

    O. A. Krzysik, B. S. Southworth, and G. A. Wimmer , A blackbox, algebraic multilevel preconditioning framework for conforming finite elements , (2026). Submitted

    2026

  16. [16]

    Lewis and G

    R. Lewis and G. Palmer , Gcol: A high-performance python library for graph colouring , Journal of Open Source Software, 10 (2025), p. 7871, https://doi.org/10.21105/joss.07871, https://doi.org/10.21105/joss.07871

    work page doi:10.21105/joss.07871 2025

  17. [17]

    S. P. MacLachlan and L. N. Olson , Theoretical bounds for algebraic multigrid performance: review and analysis , Numerical Linear Algebra with Applications, 21 (2014), pp. 194--220

    2014

  18. [18]

    Nataf, H

    F. Nataf, H. Xiang, V. Dolean, and N. Spillane , A Coarse Space Construction Based on Local Dirichlet-to-Neumann Maps , SIAM Journal on Scientific Computing, 33 (2011), pp. 1623--1642, https://doi.org/10.1137/100796376

    work page doi:10.1137/100796376 2011

  19. [19]

    T. Shen, J. Brannick, R. Falgout, K. Kahl, and J. Schroder , Nodal coarsening and sparse ideal interpolation for h (curl) problems in algebraic multigrid , arXiv preprint arXiv:2602.23613, (2026)

    arXiv 2026

  20. [20]

    B. F. Smith, P. E. Bj rstad, and W. D. Gropp , Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations , Cambridge University Press, 2004

    2004

  21. [21]

    B. S. Southworth, H. Al Daas , G. A. Wimmer, and E. Threlfall , Algebraic Multigrid with Overlapping Schwarz Smoothers and Local Spectral Coarse Grids for Least Squares Problems , arXiv preprint arXiv:2601.04112, (2026), https://arxiv.org/abs/2601.04112, https://arxiv.org/abs/2601.04112

    arXiv 2026

  22. [22]

    Spillane, V

    N. Spillane, V. Dolean, P. Hauret, F. Nataf, C. Pechstein, and R. Scheichl , Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps , Numerische Mathematik, 126 (2014), pp. 741--770, https://doi.org/10.1007/s00211-013-0576-y

    work page doi:10.1007/s00211-013-0576-y 2014

  23. [23]

    Toselli and O

    A. Toselli and O. Widlund , Domain decomposition methods-algorithms and theory , vol. 34, Springer Science & Business Media, 2004

    2004

  24. [24]

    Toselli and O

    A. Toselli and O. B. Widlund , Domain Decomposition Methods---Algorithms and Theory , vol. 34 of Springer Series in Computational Mathematics, Springer, 2005, https://doi.org/10.1007/b137868

    work page doi:10.1007/b137868 2005

  25. [25]

    Van e k, J

    P. Van e k, J. Mandel, and M. Brezina , Algebraic Multigrid by Smoothed Aggregation for Second and Fourth Order Elliptic Problems , Computing, 56 (1996), pp. 179--196, https://doi.org/10.1007/BF02238511

    work page doi:10.1007/bf02238511 1996

  26. [26]

    R. S. Varga , Matrix iterative analysis , Springer Berlin, Heidelberg, second revised and expanded edition ed., 1999, https://doi.org/10.1007/978-3-642-05156-2

    work page doi:10.1007/978-3-642-05156-2 1999

  27. [27]

    P. S. Vassilevski , Lecture notes on multigrid methods , Tech. Report LLNL-TR-439511, Lawrence Livermore National Laboratory, July 2010

    2010

  28. [28]

    and Haberland, Matt and Reddy, Tyler and Cournapeau, David and Burovski, Evgeni and Peterson, Pearu and Weckesser, Warren and Bright, Jonathan and van der Walt, Stefan J

    P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt , M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, \.I . Polat, Y. Feng, E. W. Moore, J. VanderPlas , D. Laxalde, J. Perktold, R. Cimrman, I. Henrik...

    work page doi:10.1038/s41592-019-0686-2 2020

  29. [29]

    G. A. Wimmer, B. S. Southworth, T. J. Gregory, and X.-Z. Tang , A fast algebraic multigrid solver and accurate discretization for highly anisotropic heat flux i: open field lines , SIAM journal on scientific computing, 46 (2024), pp. A1821--A1849

    2024

  30. [30]

    Xu , Iterative methods by space decomposition and subspace correction , SIAM Review, 34 (1992), pp

    J. Xu , Iterative methods by space decomposition and subspace correction , SIAM Review, 34 (1992), pp. 581--613, https://doi.org/10.1137/1034116

    work page doi:10.1137/1034116 1992

  31. [31]

    Xu , Iterative methods by space decomposition and subspace correction , SIAM review, 34 (1992), pp

    J. Xu , Iterative methods by space decomposition and subspace correction , SIAM review, 34 (1992), pp. 581--613

    1992

  32. [32]

    Xu and L

    J. Xu and L. Zikatanov , Algebraic Multigrid Methods , Acta Numerica, 26 (2017), pp. 591--721, https://doi.org/10.1017/S0962492917000083

    work page doi:10.1017/s0962492917000083 2017

  33. [33]

    Xu and C.-S

    X. Xu and C.-S. Zhang , Convergence analysis of inexact two-grid methods: A theoretical framework , SIAM Journal on Numerical Analysis, 60 (2022), pp. 133--156

    2022