Pith. sign in

REVIEW 4 minor 42 references

Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Block-sketched resolvent poles recover nonlinear eigenvalues, and zooming plus block probing make the accuracy predictable and high.

desk verdict Solid first quantitative theory for AAA-resolvent polefinding: block probing recovers multiplicities and zooming improves accuracy as predicted, with matching numerics and public code. read the letter →

arxiv 2607.10377 v1 pith:WIDJBADT submitted 2026-07-11 math.NA cs.NA

Nian Shao , Yuji Nakatsukasa This is my paper · ORCID
classification math.NAcs.NA MSC 65H1741A2065F15
keywords nonlineareigenvalueproblemrationalapproximationpolefindingsketchedresolventblockprobingzoomingbarycentricformAAAalgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper shows that the eigenvalues of a holomorphic matrix-valued function T can be read off as the poles of a good rational approximation to a block-sketched resolvent F(z) = Ω_L^* T(z)^{-1} Ω_R. Generically the poles of F are exactly the eigenvalues of T; when the block size is at least the geometric multiplicity, the partial algebraic multiplicities are visible from how the singular values of F blow up near each eigenvalue. The accuracy of those poles is limited if one works on a large domain that contains many poles. The authors prove that shrinking the domain (zooming) improves the error linearly with the diameter, while block probing further reduces the chance of missing modes and improves conditioning when several poles remain. They also prove that extracting the poles from a barycentric rational form by solving a companion generalized eigenproblem is both backward and forward stable under mild separation of the support points. The analysis turns a flexible but previously poorly understood numerical idea into a method whose error can be controlled.

What carries the argument

The sketched resolvent F(z) = Ω_L^* T(z)^{-1} Ω_R together with its barycentric rational approximant R; Keldysh's expansion supplies the Laurent coefficients whose singular-value asymptotics reveal partial multiplicities (Theorem 2.3), while Rouché and moment/Hankel arguments (Theorems 3.2, 3.4) control how poles of R track those of F.

What would settle it

On a fixed family of problems whose eigenvalues have known partial multiplicities, repeatedly zoom the domain diameter δ by factors of ten while keeping the rational residual at machine precision; if the observed pole error does not improve proportionally to δ (or to δ times u^{1/m}), the scaling claim fails.

Watch

Extended reading notes

Core claim

For a regular holomorphic matrix-valued T, the poles of a rational approximation R to the block-sketched resolvent F converge to the eigenvalues of T. With block size at least the geometric multiplicity, partial multiplicities are recovered from the singular-value growth of F; zooming and block probing improve pole accuracy linearly in domain diameter and by reducing the number of poles per subdomain; and barycentric polefinding via the companion pencil is backward and forward stable under mild support-point separation.

Load-bearing premise

When the computational domain is shrunk, the hidden constant in the pole-error bound is assumed to stay bounded; if that constant grows, the claimed linear accuracy gain with diameter can disappear.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper analyzes a nonlinear eigensolver that recovers eigenvalues of a holomorphic matrix-valued function T as poles of a rational approximation R to the block-sketched resolvent F(z)=Ω_L^H T(z)^{-1} Ω_R. Using Keldysh’s theorem it shows that, for block size at least the geometric multiplicity, the singular-value growth of F near an eigenvalue encodes the partial multiplicities (Theorem 2.3) and that block probing sharply reduces the probability of missing modes (Theorem 2.7). Convergence of poles of R is quantified by a Rouché/Walsh argument on unit-diameter domains (Theorem 3.2); a scaling argument then yields linear improvement with domain diameter under a bounded-prefactor proviso, while a moment/Hankel analysis (Theorem 3.4) explains the further gain obtained by reducing the number of poles per subdomain. Backward and forward stability of barycentric polefinding via the companion pencil are established under mild support-point separation (Theorems 4.3–4.4). Numerical tables and the butterfly NLEVP experiment confirm the predicted exponents and the benefit of block probing plus zooming.

Significance. The work supplies the first rigorous accuracy theory for resolvent-based AAA-type nonlinear eigensolvers, justifying two practical enhancements (block probing and recursive zooming) that practitioners already employ. The proofs rest on classical complex analysis, random-matrix anti-concentration and standard matrix perturbation theory; the numerical experiments are designed to test sharpness of the 1/m and linear-in-δ rates and are reproducible via public code. The stability results for barycentric rootfinding are of independent interest beyond eigenvalue computation. If the stated hypotheses hold, the paper gives a clear theoretical foundation for a flexible class of linear and nonlinear eigensolvers.

minor comments (4)
  1. After the scaling argument in §3.1 the paper correctly flags that the prefactor C_δ is assumed bounded under zooming; a short remark on geometries where this may fail (or a pointer to the few-pole analysis of Theorem 3.4 as the main practical mechanism) would make the proviso even clearer to readers.
  2. Table 3.1 and Table 3.2 would benefit from an explicit statement of the AAA residual tolerance used, so that the comparison with u^{1/m} is fully self-contained.
  3. In the proof of Theorem 4.3 the condition |z_k|=O(1) is harmless by shifting/scaling, but a one-sentence reminder that the same shift must be applied to the computed eigenvalue would avoid any ambiguity for implementers.
  4. Figure 3.2 heat maps are informative; adding a color-bar scale (or a sentence in the caption) would make the logarithmic residual levels immediately readable.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: pole-convergence and stability results are derived from classical complex analysis, random-matrix anti-concentration and matrix perturbation theory applied to the sketched resolvent and barycentric pencil.

full rationale

The paper’s central claims (Thm 2.3 on singular-value growth of the block-sketched resolvent, Thm 3.2 on pole location via Rouché + Cauchy estimates, Thm 3.4 on node-polynomial convergence from Hankel/Vandermonde moments, and Thms 4.3–4.4 on backward/forward stability of the barycentric companion pencil) are proved from first principles using Keldysh’s theorem, residue calculus, Wedin’s singular-vector perturbation and standard first-order defective-eigenvalue perturbation theory. No free parameters are fitted to data and then re-presented as predictions; the numerical tables and the butterfly experiment compare against independent references (exact poles of a diagonal matrix, polyeig). Self-citations appear only for algorithmic context (AAA, set-valued AAA, earlier resolvent-based eigensolvers) and are not load-bearing for the convergence or stability theorems. The sole explicit proviso (uniform boundedness of the zooming prefactor C_δ) is stated by the authors themselves and is not used to force the main unit-domain result. Consequently the derivation chain is self-contained and non-circular.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper is pure numerical analysis: it inherits holomorphicity/regularity of T, Keldysh’s resolvent expansion, Gaussian sketching, and AAA as a black-box near-best rational approximant. No physical free parameters. The only soft modeling choices are genericity of probes, the uniform bound on the zooming prefactor C_δ, and mild separation of AAA support points for backward stability.

assumptions (6)
  • domain assumption T is holomorphic on a domain containing the closure of D and the NEP is regular (det T(z0)≠0 for some z0 in D).
    Stated in §1; required for Keldysh expansion and for poles of the resolvent to be exactly the eigenvalues.
  • standard math Keldysh theorem: T(z)^{-1} = V_L (zI−J)^{-1} V_R^H + H(z) with H holomorphic in D.
    Invoked as Theorem 2.1; classical, used to analyze sketched poles and singular-value growth.
  • domain assumption For generic probing matrices with block size b ≥ geometric multiplicity d_i, sketching does not cancel the blow-up of the d_i singular values of F near λ_i.
    Theorem 2.3; measure-zero exceptional set; standard genericity for random probes.
  • ad hoc to paper Under domain scaling, the constant C_δ in the pole-error bound remains bounded as diameter δ→0.
    Explicitly assumed after the scaling argument in §3.1 to conclude linear improvement with δ; not proved for arbitrary pole geometries.
  • domain assumption AAA (set-valued) produces a barycentric rational R with residual O(u) on the sample set / boundary when the target is meromorphic with few poles.
    Used throughout §3–4 as the source of γ_n or ε; treated as a black box with known near-best behavior.
  • domain assumption Support points satisfy |z_k|=O(1) and at most one support point is Θ(1)-close to a computed root (condition (4.3)).
    Hypothesis of Theorem 4.3 for backward stability of the barycentric GEP; authors note it fails if two support points cluster near the root.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent." pith.science (2026). https://pith.science/paper/WIDJBADT

@misc{pith2026260710377,
  author       = {Pith},
  title        = {Pith review of: Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WIDJBADT}},
  note         = {Machine review of arXiv:2607.10377}
}
read the original abstract

Given a holomorphic matrix-valued function, the poles of its sketched resolvent are generically its eigenvalues. Once a good rational approximation of the sketched resolvent is obtained, the poles of this rational approximation typically lie close to those eigenvalues, thus providing a flexible framework for solving both linear and nonlinear eigenvalue problems. However, the accuracy of the computed eigenvalues is limited and remains poorly understood. This paper analyzes the convergence of this approach and demonstrates the effectiveness of two techniques to improve accuracy: block probing and zooming in. We also establish the backward and forward stability of polefinding for a barycentric rational form via a generalized eigenproblem. Numerical experiments demonstrate the sharpness of our theoretical results.

Figures

Figures reproduced from arXiv: 2607.10377 by the authors.

Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 2.1
Figure 2.1. Asymptotic growth of singular values for [PITH_FULL_IMAGE:figures/full_fig_p006_2_1.png] view at source ↗
Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figures from the paper (5 more)
Figure 2.2
Figure 2.2. Figure 2.2: Small ball probability (107 samples) for Pp∥Ω H LSΩR∥F ď ϵq, where S P F 100ˆ100 is a rank-two matrix with ∥S∥ “ 1 and ΩL and ΩR P F nˆb for F “ R (left) and F “ C (right). Although Theorem 2.7 only provides tail bounds for the Frobenius norm, we can also derive anal…
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p017_3.png]
Figure 3.1
Figure 3.1. Figure 3.1: Eigenvalues of butterfly problem (left) and subdomains for [PITH_FULL_IMAGE:figures/full_fig_p017_3_1.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p018_3.png]
Figure 3.2
Figure 3.2. Figure 3.2: Butterfly eigenvalue problems. The pb, Nq subfigure represents the compu￾tational result obtained using block probing of size b with sampling over subdomains of size 1{N. The heat map shows the logarithmic error between F and its rational approximation, while “dist” …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 15 canonical work pages

  1. [1]

    A. P. Austin and L. N. Trefethen , Computing eigenvalues of real symmetric matrices with rational filters in real arithmetic, SIAM J. Sci. Comput., 37 (2015), pp. A1365–A1387, https://doi.org/10.1137/140984129

    work page doi:10.1137/140984129 2015

  2. [2]

    F. L. Bauer and C. T. Fike , Norms and exclusion theorems, Numer. Math., 2 (1960), pp. 137–141, https://doi.org/10.1007/BF01386217

    work page doi:10.1007/bf01386217 1960

  3. [3]

    Beckermann , The condition number of real Vandermonde, Krylov and positive defi- nite Hankel matrices, Numer

    B. Beckermann , The condition number of real Vandermonde, Krylov and positive defi- nite Hankel matrices, Numer. Math., 85 (2000), pp. 553–577, https://doi.org/10.1007/ PL00005392

    2000

  4. [4]

    Betcke, N

    T. Betcke, N. J. Higham, V. Mehrmann, C. Schröder, and F. Tisseur , NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software, 39 (2013), pp. Art. 7, 28, https://doi.org/10.1145/2427023.2427024

    doi:10.1145/2427023.2427024 2013

  5. [5]

    Beyn , An integral method for solving nonlinear eigenvalue problems, Linear Algebra Appl., 436 (2012), pp

    W.-J. Beyn , An integral method for solving nonlinear eigenvalue problems, Linear Algebra Appl., 436 (2012), pp. 3839–3863, https://doi.org/10.1016/j.laa.2011.03.030

    doi:10.1016/j.laa.2011.03.030 2012

  6. [6]

    Blatt and R

    H.-P. Blatt and R. K. Kov achev a , Growth behavior and zero distribution of ratio- nal approximants, Constr. Approx., 34 (2011), pp. 393–420, https://doi.org/10.1007/ s00365-010-9124-5

    2011

  7. [7]

    O. P. Bruno, M. Santana, and L. N. Trefethen ,Evaluation of resonances: Adaptivity and AAA rational approximation of randomly scalarized boundary integral resolvents, SIAM J. Sci. Comput., 48 (2026), pp. A1260–A1283, https://doi.org/10.1137/24M1690680

    work page doi:10.1137/24m1690680 2026

  8. [8]

    Bujanovic and D

    Z. Bujanovic and D. Kressner , Norm and trace estimation with random rank-one vectors, SIAMJ.MatrixAnal.Appl., 42(2021), pp.202–223, https://doi.org/10.1137/20M1331718

    work page doi:10.1137/20m1331718 2021

Show all 42 references
  1. [9]

    T. Chen, E. N. Epperly, R. A. Meyer, C. Musco, and A. Rao , Does block size matter in randomized block Krylov low-rank approximation?, in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2026, pp. 1026–1046, https://doi.o...

    2026 doi

  2. [10]

    De Terán, F

    F. De Terán, F. M. Dopico, and J. Moro , First order spectral perturbation theory of square singular matrix pencils, Linear Algebra Appl., 429 (2008), pp. 548–576, https:// doi.org/10.1016/j.laa.2008.03.015

    2008 doi

  3. [11]

    https://dlmf.nist.gov/, Release 1.2.4 of 2025- 03-15, https://dlmf.nist.gov/

    NIST Digital Library of Mathematical Functions. https://dlmf.nist.gov/, Release 1.2.4 of 2025- 03-15, https://dlmf.nist.gov/. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. Mc...

    2025

  4. [12]

    Epstein, Some applications of the Mellin transform in statistics, Ann

    B. Epstein, Some applications of the Mellin transform in statistics, Ann. Math. Statistics, 19 (1948), pp. 370–379, https://doi.org/10.1214/aoms/1177730201

    1948 doi

  5. [13]

    Gautschi, On inverses of Vandermonde and confluent Vandermonde matrices, Numer

    W. Gautschi, On inverses of Vandermonde and confluent Vandermonde matrices, Numer. Math., 4 (1962), pp. 117–123, https://doi.org/10.1007/BF01386302

    1962 doi

  6. [14]

    Ga vin, A

    B. Ga vin, A. Międlar, and E. Polizzi , FEAST eigensolver for nonlinear eigenvalue prob- lems, J. Comput. Sci., 27 (2018), pp. 107–117, https://doi.org/10.1016/j.jocs.2018.05.006

    2018 doi

  7. [15]

    A. A. Gončar , On a theorem of Saff, Mat. Sb. (N.S.), 94(136) (1975), pp. 152–157, 160

    1975

  8. [16]

    I. V. Gosea and S. Güttel , Algorithms for the rational approximation of matrix-valued functions, SIAM J. Sci. Comput., 43 (2021), pp. A3033–A3054, https://doi.org/10.1137/ 20M1324727

    2021

  9. [17]

    Güttel, D

    S. Güttel, D. Kressner, and B. V andereycken , Randomized sketching of nonlinear ei- genvalue problems, SIAM J. Sci. Comput., 46 (2024), pp. A3022–A3043, https://doi.org/ 10.1137/22M153656X

    2024 doi

  10. [18]

    Güttel, G

    S. Güttel, G. M. Negri Porzio, and F. Tisseur , Robust rational approximations of nonlinear eigenvalue problems, SIAM J. Sci. Comput., 44 (2022), pp. A2439–A2463, https: //doi.org/10.1137/20M1380533

    2022 doi

  11. [19]

    Güttel and F

    S. Güttel and F. Tisseur , The nonlinear eigenvalue problem, Acta Numer., 26 (2017), pp. 1–94, https://doi.org/10.1017/S0962492917000034

    2017 doi

  12. [20]

    Güttel, R

    S. Güttel, R. V an Beeumen, K. Meerbergen, and W. Michiels , NLEIGS: a class of fully rational Krylov methods for nonlinear eigenvalue problems, SIAM J. Sci. Comput., 36 (2014), pp. A2842–A2864, https://doi.org/10.1137/130935045

    2014 doi

  13. [21]

    Ikegami, T

    T. Ikegami, T. Sakurai, and U. Nagashima , A filter diagonalization for generalized eigen- value problems based on the Sakurai-Sugiura projection method, J. Comput. Appl. Math., 233 (2010), pp. 1927–1936, https://doi.org/10.1016/j.cam.2009.09.029

    2010 doi

  14. [22]

    M. V. Keldysh , On the completeness of the eigenfunctions of some classes of non-selfadjoint linear operators, Russian Mathematical Surveys, 26 (1971), p. 15, https://doi.org/10.1070/ RM1971v026n04ABEH003985

    1971

  15. [23]

    Klein, Applications of linear barycentric rational interpolation, PhD thesis, Université de 24 NIAN SHAO AND YUJI NAKATSUKASA Fribourg, 2012

    G. Klein, Applications of linear barycentric rational interpolation, PhD thesis, Université de 24 NIAN SHAO AND YUJI NAKATSUKASA Fribourg, 2012

    2012

  16. [24]

    Kressner, Y

    D. Kressner, Y. Liu, J. E. Roman, M. Shao, and N. Shao , Linear convergence of itera- tive contour integral-based eigensolvers for nonlinear eigenvalue problems, arXiv preprint arXiv:2606.13357, (2026), https://doi.org/10.48550/arXiv.2606.13357

    2026 doi arXiv

  17. [25]

    Kressner, M

    D. Kressner, M. J. Peláez, and J. Moro ,Structured Hölder condition numbers for multiple eigenvalues, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 175–201, https://doi.org/10.1137/ 060672893

    2009

  18. [26]

    Kressner and N

    D. Kressner and N. Shao , On a randomized small-block Lanczos method for large-scale null space computations, SIAM J. Sci. Comput., (2026), https://doi.org/10.1137/24M1674881

    2026 doi

  19. [27]

    Lietaert, K

    P. Lietaert, K. Meerbergen, J. Pérez, and B. V andereycken , Automatic rational ap- proximation and linearization of nonlinear eigenvalue problems, IMA J. Numer. Anal., 42 (2022), pp. 1087–1115, https://doi.org/10.1093/imanum/draa098

    2022 doi

  20. [28]

    Mehrmann and H

    V. Mehrmann and H. Voss , Nonlinear eigenvalue problems: a challenge for modern ei- genvalue methods, GAMM Mitt. Ges. Angew. Math. Mech., 27 (2004), pp. 121–152, https://doi.org/10.1002/gamm.201490007

    2004 doi

  21. [29]

    R. A. Meyer and H. A vron , Hutchinson’s estimator is bad at Kronecker-trace-estimation, SIAMJ.MatrixAnal.Appl., 47(2026), pp.353–387, https://doi.org/10.1137/24M1720895

    2026 doi

  22. [30]

    R. A. Meyer, W. J. Sw artworth, and D. Woodruff , Understanding the Kronecker matrix-vector complexity of linear algebra, in Forty-second International Conference on Machine Learning, 2025, https://openreview.net/forum?id=2qTwKMDAsD

    2025

  23. [31]

    C. B. Moler and G. W. Stew art , An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10 (1973), pp. 241–256, https://doi.org/10.1137/0710024

    1973 doi

  24. [32]

    Nakatsukasa, O

    Y. Nakatsukasa, O. Sète, and L. N. Trefethen , The AAA algorithm for rational ap- proximation, SIAMJ.Sci.Comput., 40(2018), pp.A1494–A1522, https://doi.org/10.1137/ 16M1106122

    2018

  25. [33]

    Nakatsukasa and L

    Y. Nakatsukasa and L. N. Trefethen , Applications of AAA rational approximation, Acta Numer., 35 (2026), pp. 459–601, https://doi.org/10.1017/S0962492925100263

    2026 doi

  26. [34]

    Neumaier, Residual inverse iteration for the nonlinear eigenvalue problem, SIAM J

    A. Neumaier, Residual inverse iteration for the nonlinear eigenvalue problem, SIAM J. Nu- mer. Anal., 22 (1985), pp. 914–923, https://doi.org/10.1137/0722055

    1985 doi

  27. [35]

    Polizzi, Density-matrix-based algorithm for solving eigenvalue problems, Phys

    E. Polizzi, Density-matrix-based algorithm for solving eigenvalue problems, Phys. Rev. B, 79 (2009), p. 115112, https://doi.org/10.1103/PhysRevB.79.115112

    2009 doi

  28. [36]

    Rudelson and R

    M. Rudelson and R. Vershynin , Non-asymptotic theory of random matrices: extreme sin- gular values, in Proceedings of the International Congress of Mathematicians. Volume III, Hindustan Book Agency, New Delhi, 2010, pp. 1576–1602

    2010

  29. [37]

    Y. Saad, M. El-Guide, and A. Międlar ,A rational approximation method for the nonlinear eigenvalue problem, arXiv preprint arXiv:1901.01188, (2019), https://doi.org/10.48550/ arXiv.1901.01188

    1901 arXiv

  30. [38]

    Sakurai and H

    T. Sakurai and H. Sugiura , A projection method for generalized eigenvalue problems using numerical integration, in Proceedings of the 6th Japan-China Joint Seminar on Numeri- cal Mathematics (Tsukuba, 2002), vol. 159, 2003, pp. 119–128, https://doi.org/10.1016/ S0377-0427(03)00565-X

    2002

  31. [39]

    Shao, A structural bound for cluster robustness of randomized small-block Lanczos, arXiv preprint arXiv:2507.10144, (2025), https://doi.org/10.48550/arXiv.2507.10144

    N. Shao, A structural bound for cluster robustness of randomized small-block Lanczos, arXiv preprint arXiv:2507.10144, (2025), https://doi.org/10.48550/arXiv.2507.10144

    2025 doi arXiv

  32. [40]

    J. L. W alsh, The convergence of sequences of rational functions of best approximation, Math. Ann., 155 (1964), pp. 252–264, https://doi.org/10.1007/BF01344163

    1964 doi

  33. [41]

    Wedin, Perturbation bounds in connection with singular value decomposition, Nordisk Tidskr

    P.-A. Wedin, Perturbation bounds in connection with singular value decomposition, Nordisk Tidskr. Informationsbehandling (BIT), 12 (1972), pp. 99–111, https://doi.org/10.1007/ bf01932678

    1972

  34. [42]

    W. T. Wells, R. L. Anderson, and J. W. Cell , The distribution of the product of two central or noncentral chi-square variates, Ann. Math. Statist., 33 (1962), pp. 1016–1020, https://doi.org/10.1214/aoms/1177704469

    1962 doi

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.