pith. sign in

arxiv: 2604.21648 · v2 · submitted 2026-04-23 · 🧮 math.NA · cs.NA

Optimal transfer operators for nonsymmetric two-grid methods

Reinhard Nabben , Ludwig Rooch This is my paper

Pith reviewed 2026-05-09 21:19 UTC · model grok-4.3

classification 🧮 math.NA cs.NA MSC 65N5565F10
keywords algebraic multigridtwo-grid methodsnonsymmetric systemsoptimal transfer operatorsB-normconvergence analysisinterpolation restriction
0
0 comments X

The pith

Compatible transfer operators can be chosen optimally to minimize the error norm in nonsymmetric two-grid methods for arbitrary B-norms.

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

The paper develops a convergence theory for algebraic two-grid methods on nonsymmetric systems using general B-inner products and the induced B-norms. It analyzes two error operators: the first is the natural extension of the symmetric positive definite case, while the second is simpler yet needs an extra normality condition on the smoother. The main result constructs optimal interpolation and restriction operators for both operators that explicitly minimize the norm of the propagated error. This matters because it supplies a systematic way to build effective algebraic multigrid solvers when the matrix lacks symmetry or positive definiteness.

Core claim

We prove new convergence results for nonsymmetric algebraic two-grid methods in arbitrary B-norms. We establish optimal compatible interpolation and restriction operators for both two-grid error operators that minimize the error norm. The first operator generalizes the Hermitian case directly; the second, although simpler, requires the smoothing step M inverse A to be normal in some inner product in order for convergence to hold.

What carries the argument

Optimal compatible interpolation and restriction operators that minimize the error norm of the two-grid error operators.

If this is right

  • Convergence holds for the first error operator under the stated B-norm framework with no further assumptions.
  • The second operator converges once the normality condition on the smoother is met.
  • The optimal transfers generalize earlier results obtained for special symmetric or normal cases.
  • Algebraic multigrid can be applied to nonsymmetric indefinite systems while controlling error propagation through explicit minimization.

Where Pith is reading between the lines

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

  • These operators could be inserted into existing AMG codes for fluid-flow or convection-dominated problems to reduce iteration counts.
  • The two-grid analysis suggests a path for extending the same optimality construction to full V- or W-cycles.
  • Numerical tests on standard nonsymmetric benchmark matrices would directly measure how much smaller the error norm becomes compared with non-optimal transfers.

Load-bearing premise

The smoothing step must be normal in some inner product for the simpler error operator to achieve convergence.

What would settle it

Take a concrete nonsymmetric matrix where the smoother is not normal in any inner product, apply the second error operator with the claimed optimal transfers, and check whether the B-norm of the error fails to decrease as predicted by the convergence bound.

read the original abstract

Algebraic Multigrid (AMG) methods have been proven to be effective solvers for large-scale linear algebraic systems $Ax = b$ with Hermitian positive definite (HPD) matrix $A$. For such problems the convergence in the $A$-norm is well understood, but for nonsymmetric indefinite systems fewer results exist. Recently, convergence results for more general $B$-norms induced by certain HPD matrices were established. There, orthogonal projections built by compatible transfer operators are used. Here, we present a theoretical framework for the convergence of nonsymmetric algebraic two-grid methods for arbitrary $B$-inner products and induced $B$-norms which naturally includes the HPD case and all recent results for the nonsymmetric case. For this purpose, we consider two different two-grid error operators with the first one being the natural generalization of the error operator in the HPD case. The second operator has been studied before and is simpler, but requires the additional assumption of normality in some inner product of the smoothing step $M^{-1}A$ to achieve convergence. We prove new convergence results, generalize some previous results and explain the differences and similarities of both operators together with the necessity of the normality. Moreover, we establish optimal compatible interpolation and restriction operators for both two-grid methods that minimize the error norm.

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

2 major / 2 minor

Summary. The paper develops a theoretical framework for analyzing the convergence of nonsymmetric algebraic two-grid methods in arbitrary B-inner products and induced B-norms. It examines two error operators: the first as a natural generalization of the Hermitian positive definite (HPD) case, and the second as a simpler variant previously studied. New convergence results are proved, prior results generalized, differences between the operators explained (including the necessity of a normality assumption on the smoothing step M^{-1}A for the second operator), and optimal compatible interpolation and restriction operators are derived that minimize the error norm for both methods.

Significance. If the derivations hold, the work unifies and extends convergence theory for AMG methods beyond HPD matrices to nonsymmetric indefinite systems in general B-norms, while providing explicit optimal transfer operators. This addresses a gap where fewer results exist for nonsymmetric cases and could improve practical solver design for broader linear systems.

major comments (2)
  1. [Introduction and section on the first error operator] The abstract and introduction claim that the first error operator is the natural generalization without the normality assumption required by the second. However, the analysis of the first operator (likely in the section deriving its convergence bound) must be checked to confirm it does not implicitly rely on an equivalent condition, such as a specific choice of B-inner product or restriction on the smoothing operator, which would weaken the distinction and the generality of the new results.
  2. [Section deriving optimal transfer operators] The optimality of the compatible interpolation and restriction operators is established by minimizing the error norm. The derivation (probably involving the minimization problem in the relevant theorem) should explicitly verify that these operators remain compatible for nonsymmetric indefinite A without additional assumptions beyond those stated for the first error operator.
minor comments (2)
  1. Clarify the notation for the two error operators early in the paper to distinguish them consistently throughout the proofs and examples.
  2. Ensure all assumptions for the B-norm framework (e.g., HPD property of B) are listed explicitly before the main theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback on our manuscript. We address each major comment below with clarifications from the derivations in the paper. We believe these points can be resolved through targeted revisions that strengthen the presentation without altering the core results.

read point-by-point responses

  1. Referee: [Introduction and section on the first error operator] The abstract and introduction claim that the first error operator is the natural generalization without the normality assumption required by the second. However, the analysis of the first operator (likely in the section deriving its convergence bound) must be checked to confirm it does not implicitly rely on an equivalent condition, such as a specific choice of B-inner product or restriction on the smoothing operator, which would weaken the distinction and the generality of the new results.

    Authors: We appreciate this careful scrutiny. In Section 3, the convergence bound for the first error operator is derived directly from the general B-inner product framework and the operator's definition as the natural extension of the HPD case (via the orthogonal projection property in the B-norm). The proof uses only the triangle inequality and the contraction properties of the smoother and coarse-grid correction without invoking normality of M^{-1}A or any restriction on the choice of B beyond it being HPD. This maintains the distinction from the second operator, whose bound requires normality for the same generality. To address the concern explicitly, we will add a short remark after the main theorem in Section 3 stating the precise assumptions employed and confirming the absence of implicit normality conditions. revision: partial

  2. Referee: [Section deriving optimal transfer operators] The optimality of the compatible interpolation and restriction operators is established by minimizing the error norm. The derivation (probably involving the minimization problem in the relevant theorem) should explicitly verify that these operators remain compatible for nonsymmetric indefinite A without additional assumptions beyond those stated for the first error operator.

    Authors: We agree that an explicit verification strengthens the claim. The minimization problem in Theorem 4.1 is posed in the general B-norm, and the resulting operators are shown to satisfy the compatibility relations (P and R such that the coarse-grid correction is a projection) by direct substitution into the error operator definition. This construction holds under the framework's assumptions, which apply verbatim to nonsymmetric indefinite A without requiring symmetry, positive definiteness of A, or normality. We will revise the proof of Theorem 4.1 to include a dedicated paragraph verifying compatibility for the nonsymmetric indefinite case using only the stated hypotheses. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent proofs and standard linear algebra

full rationale

The paper establishes a theoretical framework for nonsymmetric two-grid methods in arbitrary B-norms, proving new convergence results for two distinct error operators and deriving optimal compatible transfer operators that minimize the error norm. The abstract explicitly distinguishes the first operator as the natural generalization of the HPD case and the second as simpler but requiring an additional normality assumption on the smoothing step; these are presented as separate analyses rather than reductions of one to the other. References to recent prior results on B-norms are used as background context, not as load-bearing self-citations that force the current claims by definition. No equations or steps in the provided text reduce predictions or uniqueness statements to fitted inputs or self-referential definitions. The work is self-contained against external benchmarks in numerical linear algebra.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard linear algebra assumptions about inner products and norms without introducing new free parameters or invented entities.

axioms (2)
  • domain assumption B is a Hermitian positive definite matrix that induces a valid B-inner product and B-norm
    Central to generalizing the convergence analysis beyond the HPD case.
  • domain assumption Transfer operators are compatible and satisfy the required projection properties for the two-grid error operators
    Necessary for defining and analyzing both error operators.

pith-pipeline@v0.9.0 · 5527 in / 1165 out tokens · 35751 ms · 2026-05-09T21:19:07.556923+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Norm-based convergence bounds for nonsymmetric algebraic V-cycle multigrid methods

    math.NA 2026-04 unverdicted novelty 7.0

    Norm-based convergence bounds are established for nonsymmetric algebraic V-cycle multigrid methods using B-orthogonal projections, extending McCormick's V-cycle result.

Reference graph

Works this paper leans on

39 extracted references · 28 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    A. Ali, J. J. Brannick, K. Kahl, O. A. Krzysik, J. B. Schroder, and B. S. Southworth , Generalized optimal AMG convergence theory for nonsymmetric and indefinite problems , SIAM Journal on Scientific Computing, 0 (2025), pp. S89--S111, https://doi.org/10.1137/24M1679288

    work page doi:10.1137/24m1679288 2025

  2. [2]

    Batalha and R

    M. Batalha and R. Nabben , B-orthogonal projections in the convergence analysis of nonsymmetric algebraic multigrid , to be published in SIAM J. Matrix Anal. Appl, (2026)

    2026

  3. [3]

    Benzi, A

    M. Benzi, A. Frommer, R. Nabben, and D. B. Szyld , Algebraic theory of multiplicative S chwarz methods , Numer. Math., 89 (2001), pp. 605--639, https://doi.org/10.1007/s002110100275, https://doi.org/10.1007/s002110100275

    work page doi:10.1007/s002110100275 2001

  4. [4]

    Brannick, F

    J. Brannick, F. Cao, K. Kahl, R. D. Falgout, and X. Hu , Optimal interpolation and compatible relaxation in classical algebraic multigrid , SIAM J. Sci. Comput., 40 (2018), pp. A1473--A1493, https://doi.org/10.1137/17M1123456

    work page doi:10.1137/17m1123456 2018

  5. [5]

    Brezina, T

    M. Brezina, T. Manteuffel, S. McCormick, J. Ruge, and G. Sanders , Towards adaptive smoothed aggregation ( SA ) for nonsymmetric problems , SIAM J. Sci. Comput., 32 (2010), pp. 14--39, https://doi.org/10.1137/080727336

    work page doi:10.1137/080727336 2010

  6. [6]

    Elsner and K

    L. Elsner and K. D. Ikramov , Normal matrices: an update , Linear Algebra Appl., 285 (1998), pp. 291--303, https://doi.org/10.1016/S0024-3795(98)10161-1

    work page doi:10.1016/s0024-3795(98)10161-1 1998

  7. [7]

    Faber and T

    V. Faber and T. Manteuffel , Necessary and sufficient conditions for the existence of a conjugate gradient method , SIAM Journal on Numerical Analysis, 21 (1984), pp. 352--362

    1984

  8. [8]

    R. D. Falgout and P. S. Vassilevski , On generalizing the algebraic multigrid framework , SIAM J. Numer. Anal., 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 , Numer. Linear Algebra Appl., 12 (2005), pp. 471--494, https://doi.org/10.1002/nla.437

    work page doi:10.1002/nla.437 2005

  10. [10]

    Gal \'a ntai , Projectors and Projection Methods , Springer Science & Business Media, 2004

    A. Gal \'a ntai , Projectors and Projection Methods , Springer Science & Business Media, 2004

    2004

  11. [11]

    Garc\' a Ramos, R

    L. Garc\' a Ramos, R. Kehl, and R. Nabben , Projections, deflation, and multigrid for nonsymmetric matrices , SIAM J. Matrix Anal. Appl., 41 (2020), pp. 83--105, https://doi.org/10.1137/18M1180268

    work page doi:10.1137/18m1180268 2020

  12. [12]

    García Ramos and R

    L. García Ramos and R. Nabben , On optimal algebraic multigrid methods , 2019, https://arxiv.org/abs/1906.01381

    work page arXiv 2019

  13. [13]

    Grone, C

    R. Grone, C. R. Johnson, E. M. Sa, and H. Wolkowicz , Normal matrices , Linear Algebra Appl., 87 (1987), pp. 213--225, https://doi.org/10.1016/0024-3795(87)90168-6

    work page doi:10.1016/0024-3795(87)90168-6 1987

  14. [14]

    R. A. Horn and C. R. Johnson , Matrix analysis , Cambridge University Press, Cambridge, second ed., 2013

    2013

  15. [15]

    Kehl and R

    R. Kehl and R. Nabben , Avoiding singular coarse grid systems , Linear Algebra Appl., 507 (2016), pp. 137--152, https://doi.org/10.1016/j.laa.2016.05.025, https://doi.org/10.1016/j.laa.2016.05.025

    work page doi:10.1016/j.laa.2016.05.025 2016

  16. [16]

    O. A. Krzysik, B. S. Southworth, G. A. Wimmer, A. Ali, J. Brannick, and K. Kahl , Optimal transfer operators in algebraic two-level methods for nonsymmetric and indefinite problems , 2025, https://arxiv.org/abs/2505.05598

    work page arXiv 2025

  17. [17]

    Lancaster and L

    P. Lancaster and L. Rodman , Canonical forms for hermitian matrix pairs under strict equivalence and congruence , SIAM Review, 47 (2005), pp. 407--443

    2005

  18. [18]

    Lancaster and I

    P. Lancaster and I. Zaballa , Diagonalizable quadratic eigenvalue problems , Mechanical Systems and Signal Processing, 23 (2009), pp. 1134--1144

    2009

  19. [19]

    Li , Rayleigh quotient based optimization methods for eigenvalue problems , vol

    R.-C. Li , Rayleigh quotient based optimization methods for eigenvalue problems , vol. 19 of Ser. Contemp. Appl. Math. CAM, Higher Ed. Press, Beijing, 2015, pp. 76--108, https://doi.org/10.1142/9789814675772_0004

    work page doi:10.1142/9789814675772_0004 2015

  20. [20]

    Liesen and Z

    J. Liesen and Z. Strako s , On optimal short recurrences for generating orthogonal K rylov subspace bases , SIAM Rev., 50 (2008), pp. 485--503, https://doi.org/10.1137/060662149

    work page doi:10.1137/060662149 2008

  21. [21]

    Liesen and Z

    J. Liesen and Z. Strako s , Krylov subspace methods , Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2013. Principles and analysis

    2013

  22. [22]

    Lottes , Towards robust algebraic multigrid methods for nonsymmetric problems , Springer Theses, Springer, Cham, 2017, https://doi.org/10.1007/978-3-319-56306-0

    J. Lottes , Towards robust algebraic multigrid methods for nonsymmetric problems , Springer Theses, Springer, Cham, 2017, https://doi.org/10.1007/978-3-319-56306-0. Doctoral thesis accepted by University of Oxford, UK

    work page doi:10.1007/978-3-319-56306-0 2017

  23. [23]

    S. P. MacLachlan and L. N. Olson , Theoretical bounds for algebraic multigrid performance: review and analysis , Numer. Linear Algebra Appl., 21 (2014), pp. 194--220, https://doi.org/10.1002/nla.1930

    work page doi:10.1002/nla.1930 2014

  24. [24]

    Manteuffel and B

    T. Manteuffel and B. S. Southworth , Convergence in norm of nonsymmetric algebraic multigrid , SIAM J. Sci. Comput., 41 (2019), pp. S269--S296, https://doi.org/10.1137/18M1193773

    work page doi:10.1137/18m1193773 2019

  25. [25]

    T. A. Manteuffel, S. M\" u nzenmaier, J. Ruge, and B. Southworth , Nonsymmetric reduction-based algebraic multigrid , SIAM J. Sci. Comput., 41 (2019), pp. S242--S268, https://doi.org/10.1137/18M1193761

    work page doi:10.1137/18m1193761 2019

  26. [26]

    T. A. Manteuffel, L. N. Olson, J. B. Schroder, and B. S. Southworth , A root-node-based algebraic multigrid method , SIAM J. Sci. Comput., 39 (2017), pp. S723--S756, https://doi.org/10.1137/16M1082706

    work page doi:10.1137/16m1082706 2017

  27. [27]

    T. A. Manteuffel, J. Ruge, and B. S. Southworth , Nonsymmetric algebraic multigrid based on local approximate ideal restriction ( AIR) , SIAM J. Sci. Comput., 40 (2018), pp. A4105--A4130, https://doi.org/10.1137/17M1144350

    work page doi:10.1137/17m1144350 2018

  28. [28]

    Mense and R

    C. Mense and R. Nabben , On algebraic multi-level methods for non-symmetric systems---comparison results , Linear Algebra Appl., 429 (2008), pp. 2567--2588, https://doi.org/10.1016/j.laa.2008.04.045, https://doi.org/10.1016/j.laa.2008.04.045

    work page doi:10.1016/j.laa.2008.04.045 2008

  29. [29]

    Mense and R

    C. Mense and R. Nabben , On algebraic multilevel methods for non-symmetric systems---convergence results , Electron. Trans. Numer. Anal., 30 (2008), pp. 323--345

    2008

  30. [30]

    Norm-based convergence bounds for nonsymmetric algebraic V-cycle multigrid methods

    R. Nabben and L. Rooch , Norm-based convergence bounds for nonsymmetric algebraic V -cycle multigrid methods , 2026, https://arxiv.org/abs/2604.21815

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  31. [31]

    Notay , Algebraic analysis of two-grid methods: T he nonsymmetric case , Numer

    Y. Notay , Algebraic analysis of two-grid methods: T he nonsymmetric case , Numer. Linear Algebra Appl., 17 (2010), pp. 73--96, https://doi.org/10.1002/nla.649

    work page doi:10.1002/nla.649 2010

  32. [32]

    Notay , Algebraic Theory of Two-Grid Methods , Numer

    Y. Notay , Algebraic Theory of Two-Grid Methods , Numer. Math. Theory Methods Appl., 8 (2015), pp. 168--198

    2015

  33. [33]

    Notay , Algebraic two-level convergence theory for singular systems , SIAM J

    Y. Notay , Algebraic two-level convergence theory for singular systems , SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1419--1439, https://doi.org/10.1137/15M1031539

    work page doi:10.1137/15m1031539 2016

  34. [34]

    Notay , Analysis of two-grid methods: the nonnormal case , Math

    Y. Notay , Analysis of two-grid methods: the nonnormal case , Math. Comp., 89 (2020), pp. 807--827, https://doi.org/10.1090/mcom/3460

    work page doi:10.1090/mcom/3460 2020

  35. [35]

    B. S. Southworth and T. A. Manteuffel , On compatible transfer operators in nonsymmetric algebraic multigrid , SIAM Journal on Matrix Analysis and Applications, 45 (2024), pp. 1245--1258

    2024

  36. [36]

    P. S. Vassilevski , Multilevel block factorization preconditioners , Springer, New York, 2008. Matrix-based analysis and algorithms for solving finite element equations

    2008

  37. [37]

    T. A. Wiesner, R. S. Tuminaro, W. A. Wall, and M. W. Gee , Multigrid transfers for nonsymmetric systems based on S chur complements and G alerkin projections , Numer. Linear Algebra Appl., 21 (2014), pp. 415--438, https://doi.org/10.1002/nla.1889

    work page doi:10.1002/nla.1889 2014

  38. [38]

    Acta Numer.26, 591–721 (2017)

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

    work page doi:10.1017/s0962492917000083 2017

  39. [39]

    Xu , Convergence analysis of a two-grid method for nonsymmetric positive definite problems , 2022, https://arxiv.org/abs/2204.07918

    X. Xu , Convergence analysis of a two-grid method for nonsymmetric positive definite problems , 2022, https://arxiv.org/abs/2204.07918

    work page arXiv 2022