# Computing spectra without solving eigenvalue problems

There is a rather remarkable conjecture formulated in this paper, "Computing spectra without solving eigenvalue problems," https://arxiv.org/pdf/1711.04888.pdf and in this talk by Svitlana Mayboroda at the International Congress of Mathematicians 2018 (towards the end): https://www.youtube.com/watch?v=FhPsWJL9eNQ

Namely, she considers the following eigenvalue problem (otherwise known as the Schrödinger equation): $$[-\Delta + V(x)] \psi(x) = E\psi(x)$$ with $$x\in \Omega \subset \mathbb{R}^d$$ and $$\psi({x})\Bigr|_{\partial \Omega}=0$$,and where $$V(x)$$ is a random potential (in some sense, as defined in the paper). I.e., the potential has many valleys of random location and possibly random depth, but the exact form of randomness appears unimportant.

The statement seems to be that if we solve instead the following much simpler problem $$[-\Delta + V(x)] u(x) = 1, \mbox{with } u(x)\Bigr|_{\partial \Omega}=0$$ then the $$n$$-th consecutive minimum of the function, $$u^{-1}(x)$$, dubbed localization landscape will determine with great accuracy (there is no exact statement) the $$n$$-consecutive eigenvalue as follows $$E_n \approx (1 + d/4) \inf_x u^{-1}(x)|_n$$

I wonder if there are experts here in ODE, etc, who could comment on the status of this statement/conjecture and in general this localization landscape perspective.

The conjecture seems suspicious to me, because diagonalizing and inverting operators are in different computational complexity classes (the latter - required for finding $$u$$ - is much simpler). But if it's actually true, it would have important implications for physics (I am a physicist).

• my understanding is that the reduction in computational complexity only applies to the regime of localized wave functions; the energy level spectrum then has Poissonian statistics, independent energy levels, no level repulsion --- unlike in the regime of extended (delocalized) wave functions. The approach would not reduce the computational complexity of eigenvalue calculations in a chaotic billiard (say, a Sinai or stadium). – Carlo Beenakker Aug 12 at 15:54
• The arxiv paper has 5 authors. I find the way you give credit for the work a bit misleading (unintentionally, I'm sure). – Christian Remling Aug 12 at 17:22
• The method of the "localization landscape" goes back to a 2012 publication by Filoche and Mayboroda. Much of the earlier work is discribed in this Quanta article. Oh and by the way, in the equation for $E_n$ the function $u(x)$ should be replaced by $1/u(x)$ --- the effective potential is $1/u$, so that minima of $u$ form potential barriers. – Carlo Beenakker Aug 12 at 20:44
• Thank you, Carlo, for your feedback. I am still perplexed about it. This whole localization landscape seems like a miracle. As for credit, it's a good point, but I think the math community knows what they (you) are talking about when the credit for localization landscape is universally attributed to Svitlana Mayboroda. – Victor Galitski Aug 12 at 21:42
• Also, in her ICQM talk, she suggests that the landscape actually does "know" about the entire spectrum and in particular the Weyl law is reproduced using $u^{-1}(x)$ with much better accuracy than using the bare potential. – Victor Galitski Aug 12 at 21:50

## 1 Answer

Here is how one might rationalize the computational complexity issue: in a system of size $$L$$ (for example, a chain of $$L$$ sites), a direct calculation of $$L$$ eigenvalues requires of order $$L^2 \log L$$ operations. The calculation of the localization function $$u$$ only requires of order $$L\log L$$ operations.
The scaling with $$L$$ rather than $$L^2$$ can be understood if the eigenfunctions are localized over a length $$\xi\ll L$$. One can then divide the entire system into independent segments of length only somewhat larger than $$\xi$$, and that should be sufficient to find most of the eigenvalues with good accuracy. The computational complexity of a calculation of the eigenvalues of localized eigenfunctions would then scale as $$\xi L\log L$$ rather than as $$L^2\log L$$.