pith. sign in

arxiv: 1906.08186 · v1 · pith:4TURIHIYnew · submitted 2019-06-19 · 🧮 math.NA · cs.NA

Modifying AMG coarse spaces with weak approximation property to exhibit approximation in energy norm

Xiaozhe Hu , Panayot S. Vassilevski This is my paper

Pith reviewed 2026-05-25 19:57 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Algebraic multigridCoarse spaceWeak approximation propertyEnergy normPolynomial approximationGraph Laplacian
0
0 comments X

The pith

Polynomial approximation of an energy-norm projection produces practical sparse coarse spaces that still approximate in the energy norm.

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

Standard AMG coarse spaces satisfy the weak approximation property needed for uniform two-grid convergence. The paper modifies them by applying an energy-norm projection onto the orthogonal complement of the original space so that the new spaces also approximate well in the energy norm. Because the projection uses the inverse of a well-conditioned matrix, low-degree polynomials can approximate the projection accurately enough to keep the modified coarse matrix sparse. Theory shows the resulting spaces retain the energy-norm approximation property, and the claim is checked on both discretized PDE operators and graph Laplacians.

Core claim

Projecting in the energy norm onto the orthogonal complement of a given WAP coarse space yields a modified coarse space that approximates in the energy norm; approximating that projection by polynomials, which is valid because the matrix inverse involved is well-conditioned, produces a sparse, computationally feasible modified coarse matrix that still satisfies the energy-norm approximation property.

What carries the argument

Polynomial approximation of the energy-norm projection onto the orthogonal complement of the original coarse space.

If this is right

  • The modified coarse space satisfies approximation in the energy norm.
  • The modified coarse matrix remains sparse and therefore practical to store and apply.
  • Uniform two-grid convergence rates for the AMG method are preserved.
  • The construction applies equally to matrices from PDE discretizations and to graph Laplacians.

Where Pith is reading between the lines

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

  • The same polynomial technique could be applied recursively in a multilevel setting.
  • An adaptive choice of polynomial degree based on an estimate of the matrix condition number would keep the cost minimal while guaranteeing the desired accuracy.
  • The approach might be combined with existing AMG features such as smoothed aggregation without destroying sparsity.

Load-bearing premise

The matrix inverse inside the projection operator is sufficiently well-conditioned that low-degree polynomials approximate it accurately.

What would settle it

A computation showing that the energy-norm approximation error of the modified coarse space stays above a fixed positive threshold no matter how high the polynomial degree is raised.

read the original abstract

Algebraic multigrid (AMG) coarse spaces are commonly constructed so that they exhibit the so-called weak approximation (WAP) property which is necessary and sufficient condition for uniform two-grid convergence. This paper studies a modification of such coarse spaces so that the modified ones provide approximation in energy norm. Our modification is based on the projection in energy norm onto an orthogonal complement of original coarse space. This generally leads to dense modified coarse space matrices which is hence computationally infeasible. To remedy this, based on the fact that the projection involves inverse of a well-conditioned matrix, we use polynomials to approximate the projection and, therefore, obtain a practical, sparse modified coarse matrix and prove that the modified coarse space maintains computationally feasible approximation in energy norm. We present some numerical results for both, PDE discretization matrices as well as graph Laplacian ones, which are in accordance with our theoretical results.

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 proposes modifying AMG coarse spaces that satisfy the weak approximation property (WAP) via an energy-norm projection onto the orthogonal complement of the original space, to achieve approximation in the energy norm. Since this projection generally produces dense matrices, the authors approximate it with polynomials (justified by the well-conditioned inverse involved) to obtain a sparse modified coarse matrix, prove that the approximation property is preserved, and present supporting numerical results on PDE discretizations and graph Laplacians.

Significance. If the central claims hold, the work provides a practical route to energy-norm approximation in AMG without sacrificing sparsity or computational feasibility. This is relevant for improving two-grid convergence in algebraic multigrid, particularly for large-scale linear systems arising from PDEs and graphs. The combination of a theoretical guarantee with polynomial approximation and numerical validation on two distinct problem classes is a positive aspect.

minor comments (2)
  1. The abstract and introduction would benefit from a brief statement of the polynomial degree used or the error bound derived for the approximation of the projection operator.
  2. Notation for the modified coarse space and the polynomial approximant should be introduced consistently in the first section where they appear, to aid readability for readers familiar with standard AMG notation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript, including the recognition of its theoretical guarantees combined with polynomial approximation and numerical validation on PDE and graph problems. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

Minor self-citation possible but derivation remains self-contained

full rationale

The paper starts from standard WAP coarse spaces, applies an energy-norm projection onto the orthogonal complement (yielding a dense operator), invokes the well-conditioned inverse of the relevant matrix to justify polynomial approximation for sparsity, and proves the energy-norm approximation property is preserved. This chain relies on established AMG conditioning arguments rather than any fitted parameter renamed as a prediction or a self-referential definition. No equation reduces to its own input by construction, and the central claim does not collapse to a self-citation chain. A score of 2 accounts for the possibility of routine self-citations on prior WAP results without those citations being load-bearing for the modification or the proof.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only; no free parameters or invented entities are described. Axioms are standard background assumptions in the AMG literature.

axioms (2)
  • domain assumption The weak approximation property is necessary and sufficient for uniform two-grid convergence.
    Invoked as the starting point for the modification.
  • domain assumption The projection involves the inverse of a well-conditioned matrix.
    Used to justify polynomial approximation to the projection.

pith-pipeline@v0.9.0 · 5682 in / 1149 out tokens · 25448 ms · 2026-05-25T19:57:04.529696+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

29 extracted references · 29 canonical work pages

  1. [1]

    Spectral Upscaling for Graph Laplacian Prob- lems with Application to Reservoir Simulation,

    A. Barker, C. S. Lee, and P. S. Vassilevski, “ Spectral Upscaling for Graph Laplacian Prob- lems with Application to Reservoir Simulation, ” SIAM Journal on Scientific Computing 39(5)(2017), pp. S323-S346

    work page 2017

  2. [2]

    Brandt, S

    A. Brandt, S. McCormick, and J. Ruge, ” Algbraic Multigrid (AMG) for Sparse Matrix Equa- 20 tions,” in Sparsity and Its Applications, Edited by David J. Evans, Cambridge University Press, Cambridge, 1985, pp. 257–284

    work page 1985

  3. [3]

    Spectral AMGe ( ϱAMGe),

    T. Chartier, R. Falgout, V.E. Henson, J. Jones, T. Manteuffel, S. McCormick, J. Ruge, and P.S. Vassilevski, “ Spectral AMGe ( ϱAMGe),” SIAM Journal on Scientific Computing, 25(1)(2003), pp. 1-26

    work page 2003

  4. [4]

    Adaptive smoothed aggregation (αSA) multigrid,

    M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick, and J. Ruge, “ Adaptive smoothed aggregation (αSA) multigrid,” SIAM Rev., 47(2)(2005), pp. 317-346

    work page 2005

  5. [5]

    Smoothed aggregation spectral element agglomeration AMG: SA −ρAMGe,

    M. Brezina and P. Vassilevski, “ Smoothed aggregation spectral element agglomeration AMG: SA −ρAMGe,” in Large-Scale Scientific Computing, 8th International Conference, LSSC 2011, Sozopol, Bulgaria, June 6-10th, 2011. Revised Selected Papers. Lecture Notes in Computer Science, vol. 7116, Springer, 2012, pp. 3–15

    work page 2011

  6. [6]

    An Improved Convergence Analysis of Smoothed Aggregation Algebraic Multigrid,

    M. Brezina, P. Vanˇ ek, and P. S. Vassilevski, “ An Improved Convergence Analysis of Smoothed Aggregation Algebraic Multigrid,” Numerical Linear Algebra with Applications 19(3)(2012), pp. 441-469. (published online: 2 MAR 2011, DOI: 10.1002/nla.775)

    work page doi:10.1002/nla.775 2012

  7. [7]

    The university of Florida sparse matrix collection,

    T. A. Davis and Y. Hu, “The university of Florida sparse matrix collection,” ACM Transactions on Mathematical Software, 38(1), 2011, pp. 1-25

    work page 2011

  8. [8]

    Adaptive AMG with Coarsening Based on Compatible Weighted Matching,

    P. D’Ambra and P. S. Vassilevski, “ Adaptive AMG with Coarsening Based on Compatible Weighted Matching,” Computing and Visualization in Science 16 (2013), pp. 59-76

    work page 2013

  9. [9]

    Demko, W.F

    S. Demko, W.F. Moss, and P.W. Smith, ” Decay rates of inverses of band matrices ”, Mathe- matics of Computation 43(168)(1984), pp. 491-499

    work page 1984

  10. [10]

    On Two-grid Convergence Estimates,

    R. Falgout, P. S. Vassilevski, and L. T. Zikatanov, “ On Two-grid Convergence Estimates, ” Numerical Linear Algebra with Applications, 12(5-6), 2005, pp. 471-494

    work page 2005

  11. [11]

    Additive multilevel preconditioners based on bilinear interpolation, matrix-dependent geometric coarsening and algebraic multigrid coarsening for second-order elliptic PDEs ,

    T. Grauschopf, M. Griebel, and H. Regler, “Additive multilevel preconditioners based on bilinear interpolation, matrix-dependent geometric coarsening and algebraic multigrid coarsening for second-order elliptic PDEs ,” Applied Numerical Mathematics, Multilevel Methods 23, 1997, pp. 6395

    work page 1997

  12. [12]

    A two-grid SA-AMG convergence bound that improves when increasing the polynomial degree,

    X. Hu, P. S. Vassilevski, and J. Xu, “ A two-grid SA-AMG convergence bound that improves when increasing the polynomial degree, ” Numerical Linear Algebra with Applications 23(4)(2016), pp. 746–771

    work page 2016

  13. [13]

    Kalchev, C

    D. Kalchev, C. S. Lee, U. Villa, Y. Efendiev, and P. S. Vassilevski, Upscaling of Mixed Fi- nite Element Discretization Problems by the Spectral AMGe Method, SIAM Journal on Scientific Computing 38(5) (2016), pp. A2912-A2933

    work page 2016

  14. [14]

    Parallel auxiliary space AMG for H(curl) problems,

    T. V. Kolev and P. S. Vassilevski, “Parallel auxiliary space AMG for H(curl) problems,” Journal of Computational Mathematics 27(2009), pp. 604–623

    work page 2009

  15. [15]

    Parallel auxiliary space AMG for H(div) problems ,

    T. V. Kolev and P. S. Vassilevski, “ Parallel auxiliary space AMG for H(div) problems ,”S SIAM Journal on Scientific Computing 34(2012), pp. A3079-A3098

    work page 2012

  16. [16]

    Improving the Communication Pattern in Mat-Vec Op- erations for Large Scale-free Graphs by Disaggregation,

    V. Kuhlemann and P. S. Vassilevski, “ Improving the Communication Pattern in Mat-Vec Op- erations for Large Scale-free Graphs by Disaggregation,” SIAM Journal on Scientific Com- puting 35(5)(2013), pp. S465-S486

    work page 2013

  17. [17]

    The Construction of Coarse de Rham Complexes with Improved Approximation Properties,

    I. V. Lashuk and P. S. Vassilevski, “ The Construction of Coarse de Rham Complexes with Improved Approximation Properties, ” Computational Methods in Applied Mathematics 14(2)(2014), pp. 257-303

    work page 2014

  18. [18]

    Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs ,

    J.V. Lent, R. Scheichl, I.G. Graham, “ Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs ,” Numerical Linear Algebra with Applications 16, 2009, pp. 775799

    work page 2009

  19. [19]

    Leskovec and A

    J. Leskovec and A. Krevl, “ SNAP Datasets: Stanford Large Network Dataset Collection, http: //snap.stanford.edu/data

    work page

  20. [20]

    Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver,

    Oren E. Livne and Achi Brandt, “ Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver,” SIAM Journal on Scientific Computing 34(4) (2012), pp. B499-B522

    work page 2012

  21. [21]

    Multilevel upscaling through variational coarsening ,

    S.P. MacLachlan and J.D. Moulton, “ Multilevel upscaling through variational coarsening ,” Water Resources Research 42, 2006

    work page 2006

  22. [22]

    Localization of elliptic multiscale problems,

    A. Malqvist and D. Peterseim, “ Localization of elliptic multiscale problems, ” Math. Comp., 83(290), pp. 2583-2603, 2014

    work page 2014

  23. [23]

    The Black Box Multigrid Numerical Homoge- nization Algorithm.,

    J.D. Moulton, J.E. Dendy, and J.M. Hyman, “ The Black Box Multigrid Numerical Homoge- nization Algorithm.,” Journal of Computational Physics 142, 1998, pp. 80108

    work page 1998

  24. [24]

    An algebraic multigrid method for finite element discretizations with edge elements,

    S. Reitzinger and J. Sch¨ oberl, “An algebraic multigrid method for finite element discretizations with edge elements,” Numerical Linear Algebra with Applications 9(3) (2002), pp. 223-238

    work page 2002

  25. [25]

    On two ways of stabilizing the HB multilevel methods,

    P. S. Vassilevski, “ On two ways of stabilizing the HB multilevel methods, ” SIAM Review 39(1997), 18–53

    work page 1997

  26. [26]

    Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps ,

    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 ,” Numer. Math. 126, 2014, pp. 741770. 21

    work page 2014

  27. [27]

    Coarse Spaces by Algebraic Multigrid: Multigrid Convergence and Upscaling Error Estimates,

    Panayot S. Vassilevski, “ Coarse Spaces by Algebraic Multigrid: Multigrid Convergence and Upscaling Error Estimates, ” Advances in Adaptive Data Analysis, 3(1&2), pp. 229-249, 2011

    work page 2011

  28. [28]

    Multilevel Block F actorization Preconditioners, Matrix-based Analysis and Algorithms for Solving Finite Element Equations,

    Panayot S. Vassilevski, “ Multilevel Block F actorization Preconditioners, Matrix-based Analysis and Algorithms for Solving Finite Element Equations,” Springer, New York, 2008. 514 p

    work page 2008

  29. [29]

    Algebraic multigrid methods,

    Jinchao Xu and Ludmil Zikatanov, “ Algebraic multigrid methods, ” Acta Numerica 26(2017), pp. 591-721. 22

    work page 2017