On the infinite-dimensional QR algorithm

Abstract

Spectral computations of infinite-dimensional operators are notoriously difficult, yet ubiquitous in the sciences. Indeed, despite more than half a century of research, it is still unknown which classes of operators allow for computation of spectra and eigenvectors with convergence rates and error control. Recent progress in classifying the difficulty of spectral problems into complexity hierarchies has revealed that the most difficult spectral problems are so hard that one needs three limits in the computation, and no convergence rates nor error control is possible. This begs the question: which classes of operators allow for computations with convergence rates and error control? In this paper we address this basic question, and the algorithm used is an infinite-dimensional version of the QR algorithm. Indeed, we generalise the QR algorithm to infinite-dimensional operators. We prove that not only is the algorithm executable on a finite machine, but one can also recover the extremal parts of the spectrum and corresponding eigenvectors, with convergence rates and error control. This allows for new classification results in the hierarchy of computational problems that existing algorithms have not been able to capture. The algorithm and convergence theorems are demonstrated on a wealth of examples with comparisons to standard approaches (that are notorious for providing false solutions).We also find that in some cases the IQR algorithm performs better than predicted by theory and make conjectures for future study.

References in corpus (11)

• Real Spectra in Non-Hermitian Hamiltonians Having PT Symmetry
• Making Sense of Non-Hermitian Hamiltonians
• Hofstadter's butterfly in moire superlattices: A fractal quantum Hall effect
• Direct observation of Anderson localization of matter-waves in a controlled disorder
• Localization transitions in non-Hermitian quantum mechanics
• Cloning of Dirac fermions in graphene superlattices
• Non-Hermitian Localization and Population Biology
• Distribution of Eigenvalues in Non-Hermitian Anderson Model
• Non-Hermitean Localization and De-Localization
• Non-Hermitian Localization in Biological Networks
• Eigenvalue problem meets Sierpinski triangle: computing the spectrum of a non-self-adjoint random operator

Cited by in corpus (6)

• Residual Dynamic Mode Decomposition: Robust and verified Koopmanism
• FEAST for differential eigenvalue problems
• A contour method for time-fractional PDEs and an application to fractional viscoelastic beam equations
• On symmetrizing the ultraspherical spectral method for self-adjoint problems
• Computing eigenvalues of semi-infinite quasi-Toeplitz matrices
• On the complexity of the inverse Sturm-Liouville problem