Pith. sign in

REVIEW 1 major objections 5 minor 2 cited by

The foundations of spectral computations via the Solvability Complexity Index hierarchy

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper fixes the exact limits of spectral computation: spectra of differential operators on unbounded domains are computable with certified error from point samples of coefficients, while the spectral gap problem provably is not.

desk verdict Strong, mostly self-contained SCI classifications for spectra of PDEs on unbounded domains and the spectral gap; one caveat: the no-dispersion discrete-spectrum lower bound is imported from the companion Part II. read the letter →

arxiv 1908.09592 v4 pith:POFLHFUB submitted 2019-08-26 math.SP

Matthew J. Colbrook , Anders C. Hansen This is my paper · ORCID
classification math.SP MSC 46N4047A1035P1565L1565N25
keywords SolvabilityComplexityIndexhierarchycomputationalspectraltheoryspectraofdifferentialoperatorsonunboundeddomainscertifiederrorcontrolgapproblemdiscretespectrumandmultiplicitiescomputer-assistedproofspseudospectra
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

This paper fixes, for the first time in full generality, where the foundational problems of computational spectral theory sit in the Solvability Complexity Index hierarchy, the classification of computational problems by how many limits an algorithm needs. Its central positive claim is that spectra and pseudospectra of large classes of differential operators on unbounded domains, read from point samples (or power series) of their coefficients, can be computed with certified error control by arithmetic algorithms (class $\Sigma^A_1$), while no algorithm of any computation model can achieve that with a single limit and guaranteed accuracy (class $\Delta^G_1$). The same sharp two-sided classification is proved for operators on graphs, and for the discrete problems the paper shows that testing whether a compact set meets the spectrum is $\Pi^A_2$ but not $\Delta^G_2$, that the spectral gap problem and the bottom-of-the-spectrum classification are $\Sigma^A_2$ and $\Pi^A_2$ respectively but not $\Delta^G_2$, and that computing discrete spectra and multiplicities costs two limits (three without dispersion information). Because $\Sigma^A_1$ algorithms never output points outside the true spectrum beyond a certified error, the positive results make these spectral computations admissible as rigorous computer-assisted proofs, whereas the negative results rule out computer-assisted proofs for the spectral gap problem as a general method.

What carries the argument

The load-bearing identity is $\gamma(z,A) = \min\{\sigma_1(A-zI), \sigma_1(A^*-\bar z I)\} = \|R(z,A)\|^{-1}$ (Lemma 6.4), which turns the resolvent norm—the quantity governing the spectrum—into a smallest singular value computable with finitely many arithmetic operations and comparisons. The algorithms form rectangular truncations $P_{f(n)}(A-zI)P_n$, using the known off-diagonal decay (bounded dispersion, $D_{f,n}(A) \le c_n$) to bound the truncation error, and extract singular values through positive-definiteness tests on $LDL^*$ decompositions (Sylvester's law of inertia). Certification of each output point is delivered by the input family $\{g_m\}$ of resolvent-growth bounds, $g_m(\operatorname{dist}(z,\operatorname{Sp}(A))) \le \|R(z,A)\|^{-1}$ on $B_m(0)$, through the inversion routine $\mathrm{CompInvg}$: it converts a computed lower bound on $\|R(z,A)\|^{-1}$ into an upper bound on the distance from $z$ to the spectrum. For differential operators the Hermite-function basis converts coefficient functions into matrix elements, computed from point samples by quasi-Monte Carlo quadrature (Halton sequences with the Koksma–Hlawka inequality), exploiting the Banach-algebra property of the total-variation norm; the negative results are forced by diagonal-operator constructions in which any algorithm reading finitely many matrix entries cannot distinguish operators with different spectra.

What would settle it

Run the published routine CompSpecUB with interval arithmetic on a concrete operator in $\Omega^1_{TV}$ with a known spectrum, such as $-d^2/dx^2 + x^2 + \cos(x)$ on $L^2(\mathbb{R})$ in the Hermite basis, and compare every certified distance $E_n(z)$ against the true distance $\operatorname{dist}(z,\operatorname{Sp}(T))$: one output whose certified bound is smaller than the true distance refutes the $\Sigma^A_1$ claim. For the negative classifications, the decisive test is structural: take two diagonal self-adjoint operators that agree on their first $N$ diagonal entries but whose spectra are separated by more than $2^{-N}$; the lower-bound proofs assert that any one-limit algorithm reading only finitely many evaluations must answer identically on both, so exhibiting a tower that provably separates them refutes the $\notin \Delta^G_2$ results.

Watch

Extended reading notes

Core claim

The discovery is a sharp classification of spectral computational problems, with constructive algorithms realizing every positive result. For the classes $\Omega^1_{TV}$ and $\Omega^1_{AN}$ of differential operators on $L^2(\mathbb{R}^d)$ with coefficients of bounded total variation (resp. analytic coefficients) and known resolvent growth, the maps $T \mapsto \operatorname{Sp}(T)$ and $T \mapsto \operatorname{Sp}_\epsilon(T)$ into the Attouch–Wets metric space (a metric on closed subsets measuring agreement on every bounded set) lie in $\Sigma^A_1$ yet not in $\Delta^G_1$ (Theorems 3.3 and 3.5). Arithmetic algorithms converge to the true set while certifying, for each output point, a distance to it, and no general algorithm can do the same with one limit. Theorem 3.8 transfers the $\Sigma^A_1$ classification to spectra and pseudospectra of possibly unbounded operators on graphs; Theorem 3.9 classifies the intersection decision problems as $\Pi^A_2$ but not $\Delta^G_2$; and Theorem 3.11 classifies the spectral gap problem as $\Sigma^A_2$ but not $\Delta^G_2$, even for diagonal operators, with the four-case spectral classification at the bottom of the spectrum in $\Pi^A_2$ but not $\Delta^G_2$. Theorems 3.13 and 3.15 place computing the discrete spectrum, its non-emptiness, and eigenvalue multiplicities at $\Sigma^A_2$ (resp. $\Sigma^A_3$ without bounded dispersion), with every inclusion realized by an explicit routine given as pseudocode.

Load-bearing premise

The certified spectrum algorithms work only when the user hands the algorithm a known family of functions controlling how large the resolvent can grow away from the spectrum, together with growth bounds on the operator's coefficients; those functions and bounds always exist when the spectrum is non-empty, but as input information they are indispensable, and without them the problem is not even solvable with two limits and error control.

Editorial extensions

If this is right

  • The $\Sigma^A_1$ inclusions for $\Omega^1_{TV}$ and $\Omega^1_{AN}$ give the first general guarantee that spectra of differential operators on unbounded domains can be computed from coefficient samples soundly enough for computer-assisted proofs: output is never outside the true spectrum by more than a certified, user-shrinkable error.
  • The $\notin \Delta^G_2$ classification of the spectral gap problem for diagonal self-adjoint operators means no algorithm on any computational model can return a verifiable yes/no answer to the gap question, so computer-assisted proofs of gap or gaplessness for these classes are ruled out as a general method.
  • Discrete spectra are computable by towers whose first limit lies inside the true discrete spectrum, so eigenvalues below the essential spectrum can be isolated and approximated with multiplicities and approximate eigenvectors carrying explicit bounds, even while the full spectrum remains two limits away.
  • Standard finite-section discretization is provably suboptimal for these problems: it gives at best $\Delta^A_2$ without certified error, and the paper's computational examples show it producing spectral pollution that the new rectangular-truncation algorithms avoid.
  • The same classifications extend to general separable Hilbert spaces once a basis is chosen and bounded dispersion is known (Remark 10.1), making the algorithms applicable to Schrödinger, Dirac, and Jacobi operators on graphs and lattices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The split between $\Sigma^A_1$ (known coefficient and resolvent bounds) and $\Delta^A_2$ (only relative bounds) suggests a transferable principle for other inverse problems: supplying norm bounds converts convergent-but-uncontrolled numerics into certified numerics; testing this on resonance computations or spectral measure approximation would be a direct extension.
  • The $g_m$ resolvent assumption is the practical bottleneck for non-self-adjoint problems, since for self-adjoint operators $g_m(x)=x$ is automatic; a natural next step is to develop certified algorithms that learn resolvent-growth functions adaptively during the computation rather than requiring them as input.
  • The decision classifications (spectrum intersecting a compact set, spectral gap) delineate exactly which spectral statements can be fed into automated theorem provers; one could build a formal-proof pipeline that translates a $\Sigma^A_1$ run's certificate into a machine-checkable lemma about spectral inclusion or exclusion.
  • The rectangular truncation $P_{f(n)}(A-zI)P_n$ with bounded-dispersion $f$, rather than square truncations, is a reusable algorithmic idea likely to benefit other infinite-dimensional numerical problems such as matrix functions, invariant subspaces, or Koopman-operator approximations on unbounded state spaces.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper develops the Solvability Complexity Index (SCI) hierarchy for spectral problems and establishes sharp classifications with constructive algorithms for several central problems: computing spectra and pseudospectra of differential operators on unbounded domains (Theorems 3.3 and 3.5), unbounded operators on graphs and separable Hilbert spaces (Theorem 3.8), the spectral gap and spectral classification problems (Theorem 3.11), and discrete spectra, multiplicities, and eigenspaces (Theorems 3.13–3.15). Positive results are proved via explicit towers of arithmetic algorithms, with pseudocode in Appendix A; negative results show that general one- or two-limit algorithms cannot provide the corresponding error control. The paper also supplies numerical examples illustrating the algorithms on anharmonic oscillators, PT-symmetric operators, and the Almost Mathieu operator. The primary PDE classifications are self-contained, while the sharpness of the discrete-spectrum results without dispersion relies on a companion preprint.

Significance. If the results hold, this paper makes a major contribution to the foundations of computational spectral theory. It answers long-standing open questions by showing that spectra of large classes of differential operators on unbounded domains can be computed with certified error control from point samples of coefficients, and it provides sharp SCI classifications for spectral gap, classification, and discrete-spectrum problems. The constructive nature of the proofs is a notable strength: the paper supplies concrete algorithms and pseudocode that could be used in computer-assisted proofs, and the numerical examples demonstrate practical utility. The main caveat is that the sharp /∈ Δ^G_3 lower bounds in Theorem 3.15 are not proved in this manuscript but are imported from the self-cited companion paper [41]; the primary PDE results and the bounded-dispersion discrete-spectrum results are, however, self-contained. Overall, the paper is a substantial advance in the classification program, provided the external dependency is resolved or explicitly qualified.

major comments (1)
  1. [Section 8, proof of Theorem 3.15, Step 1] The sharp lower bounds in Theorem 3.15 ({Ξ^d_1, Ω^d_1} ∉ Δ^G_3 and {Ξ^d_2, Ω^d_2} ∉ Δ^G_3) are not proven in this manuscript. Step 1 of the proof states: "For this proof we shall use one of the decision problems in [41] that were proven to have SCI^G = 3," and the referenced decision problem and its classification are neither restated nor proved here. Since these lower bounds are exactly what makes the classification sharp, the advertised results for discrete spectra without bounded dispersion in Table 1 and the abstract are conditional on the companion preprint arXiv:1908.09598. The positive Σ^A_3 towers are constructed in the paper, but the negative half is load-bearing. I recommend either including a proof of the needed SCI^G = 3 decision problem in this paper (or an appendix), or, if Part II is published, citing the published version and explicitly marking the lower bound as proven there.
minor comments (5)
  1. [Section 3.1.1] The evaluation set Λ for the differential-operator problems should be defined explicitly (e.g., all point evaluations of the coefficients and their adjoints) so that the separation condition in Definition 2.1 is satisfied; a reader cannot otherwise rule out two different coefficient functions agreeing on the oracle.
  2. [Section 7.2, proof of Theorem 3.3] In the Π^G_1 lower-bound argument, the phrase "choose n large such that Γ_n(T0) produces the guarantee Sp(T0)∩B_{1/4}(0)^c = ∅" is insufficient on its own, since this statement is trivially true for T0. One should instead use the convergence of Γ_n(T0) to {0} together with d(X_n, Γ_n) ≤ 2^{-n} to show that the guaranteed set X_n is contained in B_{1/4}(0); the argument is repairable but should be stated precisely.
  3. [Section 6, proof of Theorem 3.8] The definition of E_n(z) appears to contain a typo: "E_n(z) = CompInvg(n, γ_n(z,A), g^{-1}_{⌈|z|⌉})" should likely be "E_n(z) = CompInvg(n, γ_n(z,A), g_{⌈|z|⌉})" to match the displayed formula in Remark 6.11.
  4. [Section 10] The numerical examples would be more reproducible if the code or a link to code were provided, though this does not affect the mathematical content.
  5. [Section 4] The list of "Recent results on computing spectra" contains duplicated numbering items (ii) appearing three times; this is an editorial artifact and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: domain assumptions, constructed algorithms, and independent prior SCI results carry the derivation; self-citations do not supply the target classifications by definition.

full rationale

The paper's central classifications are constructive reductions rather than input-output equivalences. Theorems 3.3 and 3.5 build spectral algorithms from the stated hypotheses (Hermite basis core property, polynomial growth, resolvent bounds {g_m} in (3.4), point-sample or Taylor data); Proposition 7.7 computes matrix entries, Lemma 7.2 and (7.7) turn those entries into resolvent-norm estimates, and Propositions 6.5-6.6 prove Attouch-Wets convergence and Sigma^A_1 error control. The resolvent functions {g_m} are input certificates used to bound dist(z,Sp(T)), not derived from the spectrum output, so this is not a fitted-input-called-prediction pattern. The graph results in Theorems 3.8 and 3.9 follow from the same resolvent-estimate machinery with dispersion bounds as inputs; lower bounds use independent diagonal-operator arguments. The spectral gap and classification results (Theorem 3.11) use finite-section eigenvalue gaps and Lemmas 8.1 and 8.2, with no target value fed into the algorithm's definition. The discrete-spectrum positive inclusions (Theorem 3.13 and the Sigma^A_3 half of Theorem 3.15) are explicitly constructed in Section 8 from previously established essential-spectrum towers; these citations (e.g., [8]) are parameter-free prior theorems that do not assume the discrete-spectrum classification. The only load-bearing self-citation is the negative half of Theorem 3.15: 'For this proof we shall use one of the decision problems in [41] that were proven to have SCI^G = 3.' That decision problem (finitely many non-zero columns in a 0-1 matrix) is independent of discrete spectra and is used as an oracle for a contradiction, so invoking it is external evidence rather than circular derivation. The dependence on companion [41] is a self-containedness or completeness gap, not a circular one; no claim here is obtained by renaming its own input.

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

The central theorems carry no fitted numeric parameters; all inputs, such as resolvent bounds, dispersion bounds, and coefficient norm bounds, are assumptions about the operator classes rather than free parameters. The main axioms are the domain restrictions defining Omega and the external results from the SCI hierarchy literature used for the essential spectrum tower. No new physical entities are introduced.

assumptions (8)
  • domain assumption C_c^infinity(R^d) forms a core of T and T^*, with coefficients satisfying polynomial growth bounds as in assumptions (1)-(3) of Section 3.1.
    This defines the operator classes Omega and justifies the Hermite basis core argument in Proposition 7.1.
  • domain assumption Known resolvent bound functions {g_m} exist and satisfy g_m(dist(z,Sp(T))) <= ||R(z,T)||^{-1} on B_m(0), equation (3.4).
    The Sigma^A_1 error control for spectra is built from these functions via CompInvg; without them the problem is not in Delta^G_2.
  • domain assumption For graph operators, a fixed f satisfies lim_n D_{f,n}(A)=0 and a null sequence c_n with D_{f,n}(A) <= c_n is known, equation (3.9).
    Rectangular truncations and the uniform resolvent approximation in Theorem 6.7 depend on this bounded-dispersion input.
  • domain assumption For Omega^1_TV, coefficient restrictions lie in A_r with known bounds c_n from (3.6), and A_r is a Banach algebra as in Bluemlinger-Tichy.
    Quasi-Monte Carlo matrix element approximation requires known variation bounds and the product norm bound.
  • domain assumption For Omega^1_AN, analytic coefficients have known decay d_n satisfying (3.8).
    Controls truncated Taylor series remainders in the analytic matrix element computation.
  • standard math Existence of height two and height three arithmetic towers for the essential spectrum from Ben-Artzi, Colbrook, Hansen, Nevanlinna and Seidel [8].
    Invoked in the proofs of Theorems 3.13 and 3.15 for discrete spectra; the essential spectrum tower is not reproved in this paper.
  • standard math Weyl's inequality for Hermitian eigenvalue perturbation and the min-max eigenvalue approximation lemmas (Lemmas 8.1 and 8.2).
    Used to justify convergence of finite-section eigenvalue counts for multiplicities and spectral gap and classification algorithms.
  • standard math Koksma-Hlawka inequality and Halton sequence discrepancy bounds (Theorems 7.4 and 7.5).
    Used in Proposition 7.7 to approximate integrals of coefficient times Hermite products from point samples.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The foundations of spectral computations via the Solvability Complexity Index hierarchy." pith.science (2026). https://pith.science/paper/POFLHFUB

@misc{pith2026190809592,
  author       = {Pith},
  title        = {Pith review of: The foundations of spectral computations via the Solvability Complexity Index hierarchy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/POFLHFUB}},
  note         = {Machine review of arXiv:1908.09592}
}
read the original abstract

The problem of computing spectra of operators is arguably one of the most investigated areas of computational mathematics. However, the problem of computing spectra of general bounded infinite matrices has only recently been solved. We establish some of the foundations of computational spectral theory through the Solvability Complexity Index (SCI) hierarchy, an approach closely related to Smale's program on the foundations of computational mathematics and McMullen's results on polynomial root finding with rational maps. Infinite-dimensional problems yield an intricate infinite classification theory, determining which spectral problems can be solved and with what types of algorithms. We provide answers to many longstanding open questions on the existence of algorithms. For example, we show that spectra can be computed, with error control, from point sampling operator coefficients for large classes of partial differential operators on unbounded domains. Further results include: computing spectra of (possibly unbounded) operators on graphs and separable Hilbert spaces with error control; determining if the spectrum intersects a compact set; the computational spectral gap problem and computing spectral classifications at the bottom of the spectrum; and computing discrete spectra, multiplicities, eigenspaces and determining if the discrete spectrum is non-empty. Moreover, the positive results with error control can be used in computer-assisted proofs. In contrast, the negative results preclude computer-assisted proofs for classes of operators as a whole. Our proofs are constructive, yielding a library of new algorithms and techniques that handle problems that before were out of reach. We demonstrate these algorithms on challenging problems, giving concrete examples of the failure of traditional approaches (e.g., "spectral pollution") compared to the introduced techniques.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. On the computation of geometric features of spectra of linear operators on Hilbert spaces

    math.SP 2019-08 conditional novelty 8.0 of 10

    First algorithms and solvability-complexity classifications for computing Lebesgue measure, capacity, and fractal dimensions of spectra of infinite-dimensional linear operators.

  2. Computing Spectral Measures and Spectral Types

    math.SP 2019-08 conditional novelty 8.0 of 10

    First general algorithms compute spectral measures, point/continuous/singular decompositions, functional calculus, and Radon-Nikodym derivatives for self-adjoint or unitary operators with known column decay, with Solv...

Reference graph

Works this paper leans on

116 extracted references · 77 canonical work pages · cited by 2 Pith papers

  1. [41]

    M. J. Colbrook. The foundations of spectral computations via the solvability complexity index hierarchy: Part II. arXiv:1908.09598, 2019

    work page Pith review arXiv 1908

  2. [1]

    W. Arveson. Discretized CCR algebras. Journal of Operator Theory, 26(2):225–239, 1991

    1991

  3. [2]

    W. Arveson. Improper filtrations for C∗-algebras: spectra of unilateral tridiagonal operators. Acta Sci. Math. (Szeged) , 57(1- 4):11–24, 1993

    1993

  4. [3]

    W. Arveson. Noncommutative spheres and numerical quantum mechanics. In Operator algebras, mathematical physics, and low-dimensional topology, volume 5 of Res. Notes Math., pages 1–10. A K Peters, Wellesley, MA, 1993

    1993

  5. [4]

    W. Arveson. C∗-algebras and numerical linear algebra. Journal of Functional Analysis, 122(2):333–360, 1994

    1994

  6. [5]

    W. Arveson. The role ofC∗-algebras in infinite-dimensional numerical linear algebra. InC∗-algebras: 1943–1993 (San Antonio, TX, 1993), volume 167 of Contemp. Math., pages 114–129. Amer. Math. Soc., Providence, RI, 1994

    1943

  7. [6]

    T. Barakat. The asymptotic iteration method for the eigenenergies of the anharmonic oscillator potentialV (x) = Ax2α +Bx2. Physics Letters A, 344(6):411–417, 2005

    2005

  8. [7]

    Bastounis, A

    A. Bastounis, A. C. Hansen, and V . Vlacic. On computational barriers and paradoxes in estimation, regularisation and learning. Preprint, 2018

    2018

Show all 116 references
  1. [8]

    Ben-Artzi, M

    J. Ben-Artzi, M. J. Colbrook, A. C. Hansen, O. Nevanlinna, and M. Seidel. Computing Spectra – On the Solvability Complexity Index hierarchy and towers of algorithms. arXiv:1508.03280v5, 2020

    2020 arXiv

  2. [9]

    Ben-Artzi, M

    J. Ben-Artzi, M. Marletta, and F. R ¨osler. Computing scattering resonances. arXiv:2006.03368, 2020

    2006 arXiv

  3. [10]

    C. M. Bender and S. Boettcher. Real spectra in non-Hermitian Hamiltonians having PT symmetry. Physical Review Letters , 80(24):5243, 1998

    1998

  4. [11]

    C. M. Bender, D. C. Brody, and H. F. Jones. Complex extension of quantum mechanics.Physical Review Letters, 89(27):270401, 2002

    2002

  5. [12]

    C. M. Bender and S. A. Orszag. Advanced mathematical methods for scientists and engineers I: Asymptotic methods and pertur- bation theory. Springer Science & Business Media, 2013

    2013

  6. [13]

    C. M. Bender and T. T. Wu. Anharmonic oscillator. II. A study of perturbation theory in large order.Physical Review D, 7(6):1620, 1973

    1973

  7. [14]

    L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1998

    1998

  8. [15]

    L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. American Mathematical Society. Bulletin., 21(1):1–46, 1989

    1989

  9. [16]

    Bl ¨umlinger and R

    M. Bl ¨umlinger and R. F. Tichy. Topological algebras of functions of bounded variation I.Manuscripta Mathematica, 65(2):245– 255, 1989

    1989

  10. [17]

    D. Boffi, F. Brezzi, and L. Gastaldi. On the problem of spurious eigenvalues in the approximation of linear elliptic problems in mixed form. Mathematics of Computation, 69(229):121–140, 2000

    2000

  11. [18]

    D. Boffi, R. G. Duran, and L. Gastaldi. A remark on spurious eigenvalues in a square. Appl. Math. Lett., 12(3):107–114, 1999

    1999

  12. [19]

    B ¨ogli, B

    S. B ¨ogli, B. M. Brown, M. Marletta, C. Tretter, and M. Wagenhofer. Guaranteed resonance enclosures and exclosures for atoms and molecules. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 470(2171):20140488, 2014

    2014

  13. [20]

    Bombieri, S

    E. Bombieri, S. Cook, P. Deligne, C. Fefferman, J. Gray, A. Jaffe, J. Milnor, A. Wiles, and E. Witten. The Millennium Prize Problems. CMI/AMS, 2006

    2006

  14. [21]

    B ¨ottcher

    A. B ¨ottcher. Pseudospectra and singular values of large convolution operators. Journal of Integral Equations and Applications, 6(3):267–301, 1994

    1994

  15. [22]

    B ¨ottcher

    A. B ¨ottcher. Infinite matrices and projection methods. In Lectures on operator theory and its applications (Waterloo, ON, 1994), volume 3 of Fields Inst. Monogr., pages 1–72. Amer. Math. Soc., Providence, RI, 1996

    1994

  16. [23]

    B ¨ottcher, H

    A. B ¨ottcher, H. Brunner, A. Iserles, and S. P. Nørsett. On the singular values and eigenvalues of the Fox-Li and related operators. New York J. Math., 16:539–561, 2010. FOUNDATIONS OF SPECTRAL COMPUTATIONS 51

    2010

  17. [24]

    B ¨ottcher, S

    A. B ¨ottcher, S. Grudsky, and A. Iserles. Spectral theory of large Wiener–Hopf operators with complex-symmetric kernels and rational symbols. Mathematical Proceedings of the Cambridge Philosophical Society, 151(1):161–191, 2011

    2011

  18. [25]

    B ¨ottcher and B

    A. B ¨ottcher and B. Silbermann. The finite section method for Toeplitz operators on the quarter-plane with piecewise continuous symbols. Mathematische Nachrichten, 110:279–291, 1983

    1983

  19. [26]

    B ¨ottcher and B

    A. B ¨ottcher and B. Silbermann. Introduction to large truncated Toeplitz matrices . Universitext. Springer-Verlag, New York, 1999

    1999

  20. [27]

    B ¨ottcher and B

    A. B ¨ottcher and B. Silbermann. Analysis of Toeplitz operators. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2006

    2006

  21. [28]

    N. Brown. Invariant means and finite representation theory of C*-algebras. Memoirs of the American Mathematical Society, 184, 05 2003

    2003

  22. [29]

    N. P. Brown. AF embeddings and the numerical computation of spectra in irrational rotation algebras. Numer. Funct. Anal. Optim., 27(5-6):517–528, 2006

    2006

  23. [30]

    N. P. Brown. Quasi-diagonality and the finite section method. Mathematics of Computation, 76(257):339–360, 2007

    2007

  24. [31]

    N. P. Brown, K. Dykema, and D. Shlyakhtenko. Topological entropy of free product automorphisms. Acta Mathematica , 189(1):1–35, 2002

    2002

  25. [32]

    Brunner, A

    H. Brunner, A. Iserles, and S. P. Nørsett. The spectral problem for a class of highly oscillatory Fredholm integral operators. IMA Journal of Numerical Analysis, 30(1):108–130, 12 2008

    2008

  26. [33]

    Brunner, A

    H. Brunner, A. Iserles, and S. P. Nørsett. The computation of the spectra of highly oscillatory Fredholm integral operators. J. Integral Equations Applications, 23(4):467–519, 12 2011

    2011

  27. [34]

    Buffa, P

    A. Buffa, P. Houston, and I. Perugia. Discontinuous Galerkin computation of the Maxwell eigenvalues on simplicial meshes. Journal of Computational and Applied Mathematics, 204(2):317–333, 2007

    2007

  28. [35]

    Buffa and I

    A. Buffa and I. Perugia. Discontinuous Galerkin approximation of the Maxwell eigenproblem. SIAM Journal on Numerical Analysis, 44(5):2198–2226, 2006

    2006

  29. [36]

    Buffa, I

    A. Buffa, I. Perugia, and T. Warburton. The mortar-discontinuous Galerkin method for the 2D Maxwell eigenproblem. J. Sci. Comput., 40(1-3):86–114, 2009

    2009

  30. [37]

    Caliceti, S

    E. Caliceti, S. Graffi, and M. Maioli. Perturbation theory of odd anharmonic oscillators. Communications in Mathematical Physics, 75(1):51–66, 1980

    1980

  31. [38]

    Chaudhuri and M

    R. Chaudhuri and M. Mondal. Improved Hill determinant method: General approach to the solution of quantum anharmonic oscillators. Physical Review A, 43(7):3241, 1991

    1991

  32. [39]

    S. H. Christiansen and R. Winther. On variational eigenvalue approximation of semidefinite operators. IMA J. Numer. Anal. , 33(1):164–189, 2013

    2013

  33. [40]

    M. J. Colbrook. Computing spectral measures and spectral types. arXiv:1908.06721v2, 2019

    1908 arXiv

  34. [42]

    M. J. Colbrook and A. C. Hansen. On the infinite-dimensional QR algorithm. Numerische Mathematik, 143(1):17–83, 2019

    2019

  35. [43]

    M. J. Colbrook, B. Roman, and A. C. Hansen. How to compute spectra with error control. Physical Review Letters , 122(25):250201, 2019

    2019

  36. [44]

    T. S. Cubitt, D. Perez-Garcia, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528(7581):207, 2015

    2015

  37. [45]

    F. Cucker. The arithmetical hierarchy over the reals. J. Logic Comput., 2(3):375–395, 1992

    1992

  38. [46]

    E. B. Davies. Spectral enclosures and complex resonances for general self-adjoint operators. LMS J. Comput. Math. , 1:42–74, 1998

    1998

  39. [47]

    E. B. Davies. Pseudo-spectra, the harmonic oscillator and complex resonances. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci., 455(1982):585–599, 1999

    1982

  40. [48]

    E. B. Davies. A hierarchical method for obtaining eigenvalue enclosures. Math. Comp., 69(232):1435–1455, 2000

    2000

  41. [49]

    Deift, J

    P. Deift, J. Demmel, L.-C. Li, and C. Tomei. The bidiagonal singular value decomposition and Hamiltonian mechanics. SIAM journal on numerical analysis, 28(5):1463–1516, 1991

    1991

  42. [50]

    Deift, L

    P. Deift, L. C. Li, and C. Tomei. Toda flows with infinitely many variables.Journal of Functional Analysis, 64(3):358–402, 1985

    1985

  43. [51]

    Digernes, V

    T. Digernes, V . S. Varadarajan, and S. S. Varadhan. Finite approximations to quantum systems.Rev. Math. Phys., 6(4):621–648, 1994

    1994

  44. [52]

    Dorey, C

    P. Dorey, C. Dunning, and R. Tateo. Spectral equivalences, Bethe ansatz equations, and reality properties in PT -symmetric quantum mechanics. Journal of Physics A: Mathematical and General, 34(28):5679, 2001

    2001

  45. [53]

    Doyle and C

    P. Doyle and C. McMullen. Solving the quintic by iteration. Acta Mathematica, 163(3-4):151–180, 1989

    1989

  46. [54]

    D. E. Edmunds and W. D. Evans. Spectral theory and differential operators. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 1987

    1987

  47. [55]

    Fefferman and L

    C. Fefferman and L. Seco. On the energy of a large atom. Bull. Amer. Math. Soc. (N.S.), 23(2):525–530, 1990

    1990

  48. [56]

    Fefferman and L

    C. Fefferman and L. Seco. Eigenvalues and eigenfunctions of ordinary differential operators. Adv. Math., 95(2):145–305, 1992. 52 FOUNDATIONS OF SPECTRAL COMPUTATIONS

    1992

  49. [57]

    Fefferman and L

    C. Fefferman and L. Seco. Aperiodicity of the Hamiltonian flow in the Thomas-Fermi potential. Rev. Mat. Iberoamericana, 9(3):409–551, 1993

    1993

  50. [58]

    Fefferman and L

    C. Fefferman and L. Seco. The density in a one-dimensional potential. Adv. Math., 107(2):187–364, 1994

    1994

  51. [59]

    Fefferman and L

    C. Fefferman and L. Seco. The eigenvalue sum for a one-dimensional potential. Adv. Math., 108(2):263–335, 1994

    1994

  52. [60]

    Fefferman and L

    C. Fefferman and L. Seco. On the Dirac and Schwinger corrections to the ground-state energy of an atom. Adv. Math., 107(1):1– 185, 1994

    1994

  53. [61]

    Fefferman and L

    C. Fefferman and L. Seco. The density in a three-dimensional radial potential. Adv. Math., 111(1):88–161, 1995

    1995

  54. [62]

    Fefferman and L

    C. Fefferman and L. Seco. The eigenvalue sum for a three-dimensional radial potential. Adv. Math., 119(1):26–116, 1996

    1996

  55. [63]

    Fefferman and L

    C. Fefferman and L. Seco. Interval arithmetic in quantum mechanics. In Applications of interval computations (El Paso, TX, 1995), volume 3 of Appl. Optim., pages 145–167. Kluwer Acad. Publ., Dordrecht, 1996

    1995

  56. [64]

    F. M. Fern ´andez, Q. Ma, and R. Tipping. Tight upper and lower bounds for energy eigenvalues of the Schr ¨odinger equation. Physical Review A, 39(4):1605, 1989

    1989

  57. [65]

    M. E. Fisher. Yang-Lee edge singularity andφ3 field theory. Physical Review Letters, 40(25):1610, 1978

    1978

  58. [66]

    P. J. Gaudreau, R. M. Slevinsky, and H. Safouhi. Computing energy eigenvalues of anharmonic oscillators using the double exponential Sinc collocation method. Annals of Physics, 360:520–538, 2015

    2015

  59. [67]

    H. H. Goldstine, F. J. Murray, and J. von Neumann. The Jacobi method for real symmetric matrices. J. ACM, 6(1):59–96, Jan. 1959

    1959

  60. [68]

    Golinelli, T

    O. Golinelli, T. Jolicoeur, and R. Lacaze. Finite-lattice extrapolations for a Haldane-gap antiferromagnet. Physical Review B , 50(5):3037, 1994

    1994

  61. [69]

    Hales, M

    T. Hales, M. Adams, G. Bauer, T. D. Dang, J. Harrison, L. T. Hoang, C. Kaliszyk, V . Magron, S. McLaughlin, T. T. Nguyen, Q. T. Nguyen, T. Nipkow, S. Obua, J. Pleso, J. Rute, A. Solovyev, T. H. A. Ta, N. T. Tran, T. D. Trieu, J. Urban, K. Vu, and R. Zumkeller. A formal proof o...

    2017

  62. [70]

    T. C. Hales. A proof of the Kepler conjecture. Annals of Mathematics (2), 162(3):1065–1185, 2005

    2005

  63. [71]

    A. C. Hansen. On the approximation of spectra of linear operators on Hilbert spaces. Journal of Functional Analysis , 254(8):2092–2126, 2008

    2008

  64. [72]

    A. C. Hansen. Infinite-dimensional numerical linear algebra: theory and applications. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 466(2124):3539–3559, 2010

    2010

  65. [73]

    A. C. Hansen. On the solvability complexity index, the n-pseudospectrum and approximations of spectra of operators. Journal of the American Mathematical Society, 24(1):81–124, 2011

    2011

  66. [74]

    B. Helffer. Spectral theory and its applications , volume 139 of Cambridge Studies in Advanced Mathematics . Cambridge Uni- versity Press, Cambridge, 2013

    2013

  67. [75]

    Hundertmark and B

    D. Hundertmark and B. Simon. Lieb-Thirring inequalities for Jacobi matrices. Journal of Approximation Theory, 118(1):106– 130, 2002

    2002

  68. [76]

    J. Indritz. An inequality for Hermite polynomials. Proc. Amer. Math. Soc., 12:981–983, 1961

    1961

  69. [77]

    T. Kato. On the upper and lower bounds of eigenvalues. Journal of the Physical Society of Japan, 4(4-6):334–339, 1949

    1949

  70. [78]

    Laptev and Y

    A. Laptev and Y . Safarov. Szeg˝o type limit theorems. Journal of Functional Analysis, 138(2):544–559, 1996

    1996

  71. [79]

    C. Lubich. From quantum to classical molecular dynamics: reduced models and numerical analysis. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Z¨urich, 2008

    2008

  72. [80]

    Malcolm Brown, M

    B. Malcolm Brown, M. Langer, M. Marletta, C. Tretter, and M. Wagenhofer. Eigenvalue enclosures and exclosures for non-self- adjoint problems in hydrodynamics. LMS Journal of Computation and Mathematics, 13:65–81, 2010

    2010

  73. [81]

    Marletta

    M. Marletta. Neumann-Dirichlet maps and analysis of spectral pollution for non-self-adjoint elliptic PDEs with real essential spectrum. IMA J. Numer. Anal., 30(4):917–939, 2010

    2010

  74. [82]

    Marletta and R

    M. Marletta and R. Scheichl. Eigenvalues in spectral gaps of differential operators. Journal of Spectral Theory , 2(3):293–320, 2012

    2012

  75. [83]

    McMullen

    C. McMullen. Families of rational maps and iterative root-finding algorithms. Annals of Mathematics (2), 125(3):467–493, 1987

    1987

  76. [84]

    McMullen

    C. McMullen. Braiding of the attractor and the failure of iterative algorithms. Invent. Math., 91(2):259–272, 1988

    1988

  77. [85]

    Niederreiter

    H. Niederreiter. Random number generation and quasi-Monte Carlo methods , volume 63 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992

    1992

  78. [86]

    S. Olver. ApproxFun.jl v0.8. github (online) https://github.com/JuliaApproximation/ApproxFun.jl, 2018

    2018

  79. [87]

    Olver and A

    S. Olver and A. Townsend. A fast and well-conditioned spectral method. SIAM Review, 55(3):462–489, 2013

    2013

  80. [88]

    Olver and A

    S. Olver and A. Townsend. A Practical Framework for Infinite-dimensional Linear Algebra. In Proceedings of the 1st First Workshop for High Performance Technical Computing in Dynamic Languages , HPTCDL ’14, pages 57–62, Piscataway, NJ, USA, 2014. IEEE Press

    2014

  81. [89]

    Olver and M

    S. Olver and M. Webb. SpectralMeasures.jl. github (online) https://github.com/JuliaApproximation/SpectralMeasures.jl, 2018

    2018

  82. [90]

    J. Rappaz. Approximation of the spectrum of a non-compact operator given by the magnetohydrodynamic stability of a plasma. Numerische Mathematik, 28(1):15–24, 1977. FOUNDATIONS OF SPECTRAL COMPUTATIONS 53

    1977

  83. [91]

    membrane

    J. Rappaz, J. Sanchez Hubert, E. Sanchez Palencia, and D. Vassiliev. On spectral pollution in the finite element approximation of thin elastic “membrane” shells. Numerische Mathematik, 75(4):473–500, 1997

    1997

  84. [92]

    Reed and B

    M. Reed and B. Simon. Methods of modern mathematical physics. II. Fourier analysis, self-adjointness . Academic Press [Har- court Brace Jovanovich, Publishers], New York-London, 1975

    1975

  85. [93]

    Schr ¨odinger

    E. Schr ¨odinger. A method of determining quantum-mechanical eigenvalues and eigenfunctions. Proc. Roy. Irish Acad. Sect. A., 46:9–16, 1940

    1940

  86. [94]

    Schwinger

    J. Schwinger. Unitary operator bases. Proc. Nat. Acad. Sci. U.S.A., 46:570–579, 1960

    1960

  87. [95]

    Shargorodsky

    E. Shargorodsky. On the level sets of the resolvent norm of a linear operator. Bull. Lond. Math. Soc., 40(3):493–504, 2008

    2008

  88. [96]

    Shargorodsky

    E. Shargorodsky. On the limit behaviour of second order relative spectra of self-adjoint operators. Journal of Spectral Theory , 3(4):535–552, 2013

    2013

  89. [97]

    Shub and S

    M. Shub and S. Smale. On the intractability of Hilbert’s Nullstellensatz and an algebraic version ofNP ⁄=P ? Duke Mathemat- ical Journal, 81(1):47–54, 1995

    1995

  90. [98]

    Siegl and D

    P. Siegl and D. Krej ˇciˇr´ık. On the metric operator for the imaginary cubic oscillator.Physical Review D, 86(12):121702, 2012

    2012

  91. [99]

    B. Simon. Some quantum operators with discrete spectrum but classically continuous spectrum. Annals of Physics, 146(1):209– 220, 1983

    1983

  92. [100]

    Sj ¨ostrand and M

    J. Sj ¨ostrand and M. Zworski. Asymptotic distribution of resonances for convex obstacles. Acta Mathematica, 183(2):191–253, 1999

    1999

  93. [101]

    S. Smale. The fundamental theorem of algebra and complexity theory. American Mathematical Society. Bulletin. , 4(1):1–36, 1981

    1981

  94. [102]

    S. Smale. On the efficiency of algorithms of analysis. Bull. Amer. Math. Soc. (N.S.), 13(2):87–121, 1985

    1985

  95. [103]

    S. Smale. Complexity theory and numerical analysis. In Acta numerica, 1997, volume 6 of Acta Numer., pages 523–551. Cam- bridge Univ. Press, Cambridge, 1997

    1997

  96. [104]

    G. Szeg ˝o. Beitr¨age zur Theorie der Toeplitzschen Formen. Mathematische Zeitschrift, 6(3-4):167–202, 1920

    1920

  97. [105]

    T. D. Tai. On the simpleness of zeros of Stokes multipliers. Journal of Differential Equations, 223(2):351–366, 2006

    2006

  98. [106]

    G. Teschl. Jacobi operators and completely integrable nonlinear lattices, volume 72 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2000

    2000

  99. [107]

    A. V . Turbiner. Double well potential: perturbation theory, tunneling, WKB (beyond instantons).International Journal of Modern Physics A, 25(02n03):647–658, 2010

    2010

  100. [108]

    A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proc. London Math. Soc. (2) , 42(3):230–265, 1936

    1936

  101. [109]

    Webb and S

    M. Webb and S. Olver. Spectra of Jacobi operators via connection coefficient matrices. arXiv:1702.03095, 2017

    2017 arXiv

  102. [110]

    Weinberger

    S. Weinberger. Computers, Rigidity, and Moduli: The Large-Scale Fractal Geometry of Riemannian Moduli Space . Princeton University Press, USA, 2004

    2004

  103. [111]

    E. J. Weniger. A convergent renormalized strong coupling perturbation expansion for the ground state energy of the quartic, sextic, and octic anharmonic oscillator. Annals of Physics, 246(1):133–165, 1996

    1996

  104. [112]

    H. Weyl. The theory of groups and quantum mechanics. Dover Publications, Inc., New York, 1950

    1950

  105. [113]

    Z. Zhang. How many numerical eigenvalues can we trust? Journal of Scientific Computing, 65(2):455–466, 2015

    2015

  106. [114]

    S. Zhao. On the spurious solutions in the high-order finite difference methods for eigenvalue problems. Computer methods in applied mechanics and engineering, 196(49-52):5031–5046, 2007

    2007

  107. [115]

    M. Zworski. Resonances in physics and geometry. Notices Amer. Math. Soc., 46(3):319–328, 1999

    1999

  108. [116]

    Does there exist somez∈Kn2 such thatγn1(z,A )< 1/2n2?

    M. Zworski. Scattering resonances as viscosity limits. In Algebraic and Analytic Microlocal Analysis, pages 635–654. Springer, 2013. 54 FOUNDATIONS OF SPECTRAL COMPUTATIONS APPENDIX A. C OMPUTATIONAL ROUTINES We provide pseudocode for the algorithms of this paper, all of which...

    2013

Pith tools

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