How to Compute Spectra with Error Control

Computing the spectra of operators is a fundamental problem in the sciences, with wide-ranging applications in condensed-matter physics, quantum mechanics and chemistry, statistical mechanics, etc. While there are algorithms that in certain cases converge to the spectrum, no general procedure is known that (a) always converges, (b) provides bounds on the errors of approximation, and (c) provides approximate eigenvectors. This may lead to incorrect simulations. It has been an open problem since the 1950s to decide whether such reliable methods exist at all. We affirmatively resolve this question, and the algorithms provided are optimal, realizing the boundary of what digital computers can achieve. Moreover, they are easy to implement and parallelize, offer fundamental speed-ups, and allow problems that before, regardless of computing power, were out of reach. Results are demonstrated on difficult problems such as the spectra of quasicrystals and non-Hermitian phase transitions in optics.

Figure 1

Top: Large-scale experiment with $n={10}^5$ for the algorithm and finite section with open boundary conditions and periodic approximants ($n=64079$). The top shows an enlarged section and the high resolution obtained. The approximation computed with the finite section methods produces spurious points in band gaps with large errors $\sim 0.2$. Bottom: The maximum errors as well as time of outputs for the algorithm (blue) and finite section methods (red for open boundary conditions, green for periodic).

Figure 2

The ground state for the Penrose Laplacian and a state corresponding to energy nearest $-5$. The algorithm allows us to choose which states to compute.

Figure 3

Comparison of the finite section method and the algorithm for the magnetic Hamiltonian. The algorithm correctly leaves out the gaps and is able to capture the complicated structure with guaranteed error maximum 0.058 for $n=5000$.

Figure 4

Top: Pseudospectra of $H$ computed with the proposed algorithm and finite sections (spectrum in magenta). Bottom: Fragile $PT$-symmetric phase as we increase the system size due to edge states (caused by spectral pollution) with complex eigenvalues, verifying the unsuitability of algorithms based on finite sections.