REVIEW 6 minor 1 cited by
Auxiliary space theory for the analysis of iterative methods for semidefinite linear systems
T0 review · 0 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper proves that for semidefinite linear systems, every iterative method of the form $u_{m+1}=u_m+B(f-Au_m)$ whose operator $B$ factors through an auxiliary space satisfies an exact, constant-free formula for its convergence rate and…
desk verdict Solid, honest theory paper: the new semi-SPD auxiliary space identities are correct and unifying, but the 'unified framework' claim overreaches the factorization assumption and the applications mostly repackage known results. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the factorization identity $B=\Pi B_e\Pi^t$ together with the symmetrized auxiliary operator $\bar B_e=B_e+B_e^t-B_e^tA_eB_e$, where $A_e=\Pi^t A\Pi$ and $\Pi:V_e\to V$ is surjective. The auxiliary space lemma, $(B^{-1}v,v)=\inf_{\Pi v_e=v}(B_e^{-1}v_e,v_e)$, converts inversion in the original space into an infimum over preimages in the auxiliary space; applying this to $\bar B$ or to $B$ in the abstract symmetric-positive-definite identities of Theorem 2.3 yields the sharp formulas. The semidefinite case enters by choosing $V_e=V$ and $\Pi=Q$, the orthogonal projection onto $R(A)$, making (1.1) the auxiliary system of the restricted SPD problem (4.1); the null-space infimum in the final formulas records the freedom in the kernel of $A$.
What would settle it
Take $A=\mathrm{diag}(1,0)$ on $\mathbb{R}^2$, let $\Pi:\mathbb{R}\to\mathbb{R}^2$ be any nonzero column, and let $B_e$ be a positive scalar. Form $B=\Pi B_e\Pi^t$; compute $|I-BA|_A^2$ directly by maximizing $|(I-BA)v|_A^2$ over $v\in R(A)$ with $|v|_A=1$, and compare it with the right-hand side of Theorem 5.1. Any mismatch would refute the identity, and repeating the test over random $\Pi$ and $B_e$ would probe the factorization's sufficiency as well.
Extended reading notes
Core claim
The central discovery is an exact identity for the error propagation of the iteration. Let $A$ be symmetric positive semidefinite on a finite-dimensional space $V$, and suppose the iteration operator satisfies $B=\Pi B_e\Pi^t$ for a surjective $\Pi:V_e\to V$ and an auxiliary operator $B_e$ whose symmetrized form $\bar B_e=B_e+B_e^t-B_e^tA_eB_e$, with $A_e=\Pi^t A\Pi$, is positive definite. Then the iteration (1.2) converges in the $A$-seminorm and $$|I-BA|$_A^{2}$=1-\left(\sup_{v\in R(A),|v|_A=1}\inf_{\phi\in N(A)}\inf_{v_e\in V_e,\Pi v_e=v+\phi}(\bar $B_e^{{-1}}$v_e,v_e)\right)^{-1}.$$ The same auxiliary-space mechanism supplies matching formulas for the smallest nonzero and largest eigenvalues of $BA$ when $B_e$ is positive definite, and a relaxed version in which positive definiteness is required only on a subspace containing $R(A_e)$. The semidefinite case arises by regarding the original singular system as the auxiliary system of its own restriction to $R(A)$; the extra infimum over $\phi\in N(A)$ is the trace of the singular kernel.
Load-bearing premise
The central assumption is that the iteration operator $B$ can be factored through a surjective auxiliary map as $B=\Pi B_e\Pi^t$, with the symmetrized auxiliary operator $\bar B_e$ positive definite on $V_e$ (or on a subspace $W_f$ containing $R(A_e)$); if $B$ does not have such a factorization, the paper's exact formulas do not apply.
Editorial extensions
If this is right
- For any iterative method of the form (1.2) whose $B$ admits the factorization, the convergence rate in the $A$-seminorm is known exactly from Theorem 5.1, with no undetermined constants.
- The condition-number formulas of Theorems 5.2 and 5.4 make the analysis of preconditioned conjugate gradient methods on singular systems a matter of evaluating one auxiliary-space infimum.
- The successive subspace correction method converges on semidefinite systems whenever each restricted local solver is convergent, and the sharp Xu–Zikatanov identity (6.16) holds in this setting.
- The Hiptmair–Xu preconditioners for $H(\mathrm{curl})$ and $H(\mathrm{div})$ problems have uniformly bounded condition number by the same argument in both the definite case $\epsilon>0$ and the semidefinite case $\epsilon=0$.
- An auxiliary grid preconditioner is condition-number equivalent to the preconditioner on the structured auxiliary grid, so optimal structured-grid solvers transfer to unstructured grids.
Reading between the lines
- Not in the paper: the identity could be turned into a design principle — choose $V_e$, $\Pi$, and $B_e$ to minimize the sup-inf expression, giving a variational route to optimize preconditioners rather than merely analyze them.
- Not in the paper: because the formulas are algebraic and finite-dimensional, numerical evaluation of the right-hand side on small problems could certify a proposed factorization's convergence rate, possibly offering an a posteriori check for multigrid and domain decomposition methods.
- Not in the paper: one might test whether the theory extends to infinite-dimensional Hilbert spaces when $B$ is a bounded operator and $B_e$ is coercive on $R(A_e)$; the finite-dimensional proof does not by itself cover that case.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops an auxiliary-space framework for analyzing iterative methods of the form u_{m+1}=u_m+B(f-Au_m) for symmetric positive semidefinite linear systems. The central object is a factorization B=Π B_e Π^t through an auxiliary space V_e; under SPD assumptions on B_e or its symmetrized version, the authors derive exact identities for the error-propagation seminorm |I-BA|_A and for the extremal eigenvalues of BA, with the semidefinite case involving an additional infimum over N(A). Sections 3–5 build the abstract theory as a sequence of corollaries of the SPD auxiliary-space theorem; Section 4 recovers the semidefinite theory for general B by a canonical choice of auxiliary space; Sections 6–8 apply the framework to parallel and successive subspace correction methods, Hiptmair–Xu preconditioners, and auxiliary grid methods, yielding the Xu–Zikatanov identity and uniform condition-number bounds as special cases.
Significance. If the results hold—and the derivations appear sound—the paper provides a clean, elementary unification of several sharp convergence analyses that previously required separate arguments. Its main strengths are the exact identities rather than estimates with undetermined constants, the careful reduction of the semidefinite theory to the SPD case, and the uniform derivation of known results such as the Xu–Zikatanov identity and Hiptmair–Xu optimality. The treatment in Section 6 avoids pseudoinverses, which is a genuine pedagogical advantage. The formal contribution is a useful organizing theorem rather than a fundamentally new class of methods, but the unified viewpoint and the extension to semidefinite problems justify publication after minor revision.
minor comments (6)
- [Abstract and §5 (Eq. (3.2b))] The statement that the framework is 'unified' should be qualified with one sentence noting that every B admits the trivial factorization V_e=V, Π=I, B_e=B, while the sharp auxiliary-space identities are most useful when a factorization with a simple, SPD B_e on a larger space is available; this would address the otherwise unstated completeness question for the factorization assumption.
- [§5, Theorem 5.2] The proof of Theorem 5.2 is omitted with the sentence 'the proof is omitted, as it follow from an argument analogous to that of Theorem 5.1'; please supply a brief proof or expand the remark to say explicitly that the same substitution used in Theorem 5.1 applies with B_e in place of \bar{B}_e and with Theorem 3.6 replacing Theorem 3.5.
- [§5, paragraph before Theorem 5.3] The sentence 'We also present counterparts of Theorems 3.7 and 3.8 for the semi-SPD case, given in Theorems 4.7 and 5.3, respectively' misstates the pairing: Theorem 4.6 and Theorem 5.3 correspond to Theorem 3.7, while Theorem 4.7 and Theorem 5.4 correspond to Theorem 3.8.
- [§7.3, Theorem 7.3] The proof of Theorem 7.3 is omitted with the explanation that it is 'nearly identical' to that of Theorem 7.1; since H(div) is one of the three advertised applications, please include at least a proof sketch indicating how the discrete regular decomposition (7.5) and Theorem 5.2 are used in both the ϵ>0 and ϵ=0 cases.
- [§8, after Eq. (8.3)] 'the conditioner number κ(BA)' should read 'the condition number κ(BA)'.
- [§6, proof of Theorem 6.7] In the verification of (6.16c), the phrase 'where the last inequality is due to (6.15)' should say 'where the last equality is due to (6.15)'.
Circularity Check
No significant circularity: B = ΠB_eΠ^t is a stated representability assumption (Eq. 3.2b), and the sharp identities are proved from prior lemmas rather than assumed; same-author citations are building blocks, not forced choices.
full rationale
The derivation chain is not circular. The factorization B = ΠB_eΠ^t is introduced as an explicit representation of the method in (3.2b) and is used as a hypothesis in Theorems 3.5, 3.6, 5.1, and 5.2; it is not derived from the convergence identities, so the identities are conditional results, not restatements of the assumption. The main sharp identities are proved by applying the existing SPD theory (Theorem 2.3, quoted from [38]) together with the auxiliary space lemma (Lemma 3.1) to the auxiliary system; the semidefinite case in Section 4 follows by the special choice V_e = V, Π = Q, B_e = B, and Theorem 5.1 is derived from Theorem 3.5 with Π replaced by QΠ. This is a genuine special-case deduction, not an assumption of the target formula. The same-author citations ([7, 35, 37, 38]) are standard, parameter-free building blocks whose hypotheses do not include the semidefinite auxiliary-space identities being proved, so they do not make the argument circular. The applications verify the framework's hypotheses (factorability of B_PSC and B_SSC in Propositions 6.1 and 6.4, SPD of restricted local solvers, Hiptmair-Xu regular decompositions, and auxiliary-grid interpolation estimates), and Theorem 6.7 re-derives the known Xu-Zikatanov identity from the framework, which is an independent consistency check rather than circularity. Some proofs are omitted as analogous (e.g., Theorem 5.2 and Theorem 7.3), but an omitted proof is a completeness concern, not evidence that the result was assumed. There are no fitted parameters or empirical predictions in the paper, so the fit-based circularity patterns do not apply. The only caveat is the scope limitation noted by the skeptical reading: without a converse, the identities apply only to methods admitting the factorization (3.2b), but this is a stated assumption, not circular reasoning.
Assumptions & free parameters
assumptions (6)
- standard math Theorem 2.3 (symmetrized operator characterization of convergence for SPD systems), imported from Xu-Zikatanov [38, Theorem 4.1] without proof.
- standard math Lemma 3.1 (auxiliary space lemma): for B = Pi B_e Pi^t with B_e SPD, (B^{-1}v,v) = inf_{v_e: Pi v_e = v} (B_e^{-1} v_e, v_e).
- domain assumption Discrete regular decompositions for H_h(curl) and H_h(div) (Eqs. (7.4)-(7.5)) from Hiptmair-Xu [15].
- domain assumption Interpolation estimates for the auxiliary grid method (Eqs. (8.1a)-(8.1b)) from Xu [36, Lemmas 4.1-4.2].
- domain assumption Boundedness of canonical interpolation and inverse-inequality, finite-overlap, and coloring arguments (Section 7.1, Eq. (7.3)).
- domain assumption A is symmetric positive semidefinite, f lies in R(A), and V is finite-dimensional with a fixed inner product (Section 1.1 and Eq. (1.1)).
Cite this review
Pith. "Pith review of Auxiliary space theory for the analysis of iterative methods for semidefinite linear systems." pith.science (2026). https://pith.science/paper/DJPELRAQ
@misc{pith2026250907179,
author = {Pith},
title = {Pith review of: Auxiliary space theory for the analysis of iterative methods for semidefinite linear systems},
year = {2026},
howpublished = {\url{https://pith.science/paper/DJPELRAQ}},
note = {Machine review of arXiv:2509.07179}
}
read the original abstract
We present an auxiliary space theory that provides a unified framework for analyzing various iterative methods for solving linear systems that may be semidefinite. By interpreting a given iterative method for the original system as an equivalent, yet more elementary, iterative method for an auxiliary system defined on a larger space, we derive sharp convergence estimates using elementary linear algebra. In particular, we establish identities for the error propagation operator and the condition number associated with iterative methods, which generalize and refine existing results. The proposed auxiliary space theory is applicable to the analysis of numerous advanced numerical methods in scientific computing. To illustrate its utility, we present three examples -- subspace correction methods, Hiptmair--Xu preconditioners, and auxiliary grid methods -- and demonstrate how the proposed theory yields refined analyses for these cases.
Forward citations
Cited by 1 Pith paper
-
A polynomial dimension-dependence analysis of Bramble--Pasciak--Xu preconditioners
Under convex-mesh assumptions, BPX preconditioner condition numbers for P1 finite elements grow at most polynomially in spatial dimension d, with explicit constants.
Reference graph
Works this paper leans on
- [38]
-
[1]
B. Ayuso de Dios, F. Brezzi, L. D. Marini, J. Xu, and L. Zikatanov , A simple preconditioner for a discontinuous G alerkin method for the S tokes problem , J. Sci. Comput., 58 (2014), pp. 517--547
work page 2014
-
[2]
J. H. Bramble, J. E. Pasciak, and J. Xu , Parallel multilevel preconditioners , Math. Comp., 55 (1990), pp. 1--22
work page 1990
-
[3]
S. C. Brenner , An additive analysis of multiplicative S chwarz methods , Numer. Math., 123 (2013), pp. 1--19
work page 2013
-
[4]
S. C. Brenner and L. R. Scott , The Mathematical Theory of Finite Element Methods , Springer, New York, third ed., 2008
2008
- [5]
-
[6]
Z.-H. Cao , On the convergence of general stationary linear iterative methods for singular linear systems , SIAM J. Matrix Anal. Appl., 29 (2008), pp. 1382--1388
work page 2008
-
[7]
L. Chen , Deriving the X -- Z identity from auxiliary space method , in Domain Decomposition Methods in Science and Engineering XIX , vol. 78 of Lect. Notes Comput. Sci. Eng., Springer, Heidelberg, 2011, pp. 309--316
work page 2011
Show all 40 references
-
[8]
L. Chen, J. Hu, and X. Huang , Fast auxiliary space preconditioners for linear elasticity in mixed form , Math. Comp., 87 (2018), pp. 1601--1633
2018
-
[9]
L. Chen, J. Wang, Y. Wang, and X. Ye , An auxiliary space multigrid preconditioner for the weak G alerkin method , Comput. Math. Appl., 70 (2015), pp. 330--344
2015
-
[10]
D. Cho, J. Xu, and L. Zikatanov , New estimates for the rate of convergence of the method of subspace corrections , Numer. Math. Theory, Methods Appl., 1 (2008), pp. 44--56
2008
-
[11]
Gopalakrishnan, M
J. Gopalakrishnan, M. Neum\" u ller, and P. S. Vassilevski , The auxiliary space preconditioner for the de R ham complex , SIAM J. Numer. Anal., 56 (2018), pp. 3196--3218
2018
-
[12]
Grasedyck, L
L. Grasedyck, L. Wang, and J. Xu , A nearly optimal multigrid method for general unstructured grids , Numer. Math., 134 (2016), pp. 637--666
2016
-
[13]
Hayami , Convergence of the conjugate gradient method on singular systems , arXiv preprint arXiv:1809.00793, (2018)
K. Hayami , Convergence of the conjugate gradient method on singular systems , arXiv preprint arXiv:1809.00793, (2018)
2018 arXiv
-
[14]
Hiptmair , Finite elements in computational electromagnetism , Acta Numer., 11 (2002), pp
R. Hiptmair , Finite elements in computational electromagnetism , Acta Numer., 11 (2002), pp. 237--339
2002
-
[15]
Hiptmair and J
R. Hiptmair and J. Xu , Nodal auxiliary space preconditioning in H ( curl ) and H ( div ) spaces , SIAM J. Numer. Anal., 45 (2007), pp. 2483--2509
2007
-
[16]
Hiptmair and J
R. Hiptmair and J. Xu , Auxiliary space preconditioning for edge elements , IEEE Trans. Magn., 44 (2008), pp. 938--941
2008
-
[17]
Hu , Convergence of the H iptmair-- X u preconditioner for M axwell's equations with jump coefficients (i): E xtensions of the regular decomposition , SIAM J
Q. Hu , Convergence of the H iptmair-- X u preconditioner for M axwell's equations with jump coefficients (i): E xtensions of the regular decomposition , SIAM J. Numer. Anal., 59 (2021), pp. 2500--2535
2021
-
[18]
Hu , Convergence of the H iptmair-- X u preconditioner for H ( curl ) -elliptic problems with jump coefficients (ii): M ain results , SIAM J
Q. Hu , Convergence of the H iptmair-- X u preconditioner for H ( curl ) -elliptic problems with jump coefficients (ii): M ain results , SIAM J. Numer. Anal., 61 (2023), pp. 2434--2459
2023
-
[19]
X. Hu, J. Xu, and C. Zhang , Application of auxiliary space preconditioning in field-scale reservoir simulation , Sci. China Math., 56 (2013), pp. 2737--2751
2013
-
[20]
Jiang, J
B. Jiang, J. Park, and J. Xu , Connections between convex optimization algorithms and subspace correction methods , arXiv preprint arXiv:2505.09765, (2025)
2025 arXiv
-
[21]
E. F. Kaasschieter , Preconditioned conjugate gradients for solving singular systems , J. Comput. Appl. Math., 24 (1988), pp. 265--275
1988
-
[22]
T. V. Kolev and P. S. Vassilevski , Parallel auxiliary space AMG for H ( curl ) problems , J. Comput. Math., 27 (2009), pp. 604--623
2009
-
[23]
T. V. Kolev and P. S. Vassilevski , Parallel auxiliary space AMG solver for H ( div ) problems , SIAM J. Sci. Comput., 34 (2012), pp. A3079--A3098
2012
-
[24]
Lee and J
Y.-J. Lee and J. Park , Parallel subspace correction methods for semicoercive and nearly semicoercive convex optimization with applications to nonlinear PDE s , arXiv preprint arXiv:2412.17318, (2024)
2024
-
[25]
Y.-J. Lee, J. Wu, J. Xu, and L. Zikatanov , On the convergence of iterative methods for semidefinite linear systems , SIAM J. Matrix Anal. Appl., 28 (2006), pp. 634--641
2006
-
[26]
Y.-J. Lee, J. Wu, J. Xu, and L. Zikatanov , A sharp convergence estimate for the method of subspace corrections for singular systems of equations , Math. Comp., 77 (2008), pp. 831--850
2008
-
[27]
Li and X
B. Li and X. Xie , BPX preconditioner for nonstandard finite element methods for diffusion problems , SIAM J. Numer. Anal., 54 (2016), pp. 1147--1168
2016
-
[28]
Lions , On the S chwarz alternating method
P.-L. Lions , On the S chwarz alternating method. I , in First I nternational S ymposium on D omain D ecomposition M ethods for P artial D ifferential E quations ( P aris, 1987), SIAM, Philadelphia, PA, 1988, pp. 1--42
1987
-
[29]
S. V. Nepomnyaschikh , Decomposition and fictitious domains methods for elliptic boundary value problems , in Fifth I nternational S ymposium on D omain D ecomposition M ethods for P artial D ifferential E quations ( N orfolk, VA , 1991), SIAM, Philadelphia, PA, 1992, pp. 62--72
1991
-
[30]
Park , Additive S chwarz methods for convex optimization as gradient methods , SIAM J
J. Park , Additive S chwarz methods for convex optimization as gradient methods , SIAM J. Numer. Anal., 58 (2020), pp. 1495--1530
2020
-
[31]
Saad , Iterative Methods for Sparse Linear Systems , SIAM, Philadelphia, PA, second ed., 2003
Y. Saad , Iterative Methods for Sparse Linear Systems , SIAM, Philadelphia, PA, second ed., 2003
2003
-
[32]
Toselli and O
A. Toselli and O. Widlund , Domain Decomposition Methods---Algorithms and Theory , Springer, Berlin, 2005
2005
-
[33]
L. Wang, X. Hu, J. Cohen, and J. Xu , A parallel auxiliary grid algebraic multigrid method for graphic processing units , SIAM J. Sci. Comput., 35 (2013), pp. C263--C283
2013
-
[34]
Wu, Y.-J
J. Wu, Y.-J. Lee, J. Xu, and L. Zikatanov , Convergence analysis on iterative methods for semidefinite systems , J. Comput. Math., 26 (2008), pp. 797--815
2008
-
[35]
Xu , Iterative methods by space decomposition and subspace correction , SIAM Rev., 34 (1992), pp
J. Xu , Iterative methods by space decomposition and subspace correction , SIAM Rev., 34 (1992), pp. 581--613
1992
-
[36]
Xu , The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids , Computing, 56 (1996), pp
J. Xu , The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids , Computing, 56 (1996), pp. 215--235
1996
-
[37]
Xu and L
J. Xu and L. Zikatanov , The method of alternating projections and the method of subspace corrections in H ilbert space , J. Amer. Math. Soc., 15 (2002), pp. 573--597
2002
-
[39]
Zhang and J
S. Zhang and J. Xu , Optimal solvers for fourth-order PDE s discretized on unstructured grids , SIAM J. Numer. Anal., 52 (2014), pp. 282--307
2014
-
[40]
Zhang , Multilevel S chwarz methods , Numer
X. Zhang , Multilevel S chwarz methods , Numer. Math., 63 (1992), pp. 521--539
1992
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.