Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix

Abstract

We prove universality for the fluctuations of the halting time for the Toda algorithm to compute the largest eigenvalue of real symmetric and complex Hermitian matrices. The proof relies on recent results on the statistics of the eigenvalues and eigenvectors of random matrices (such as delocalization, rigidity and edge universality) in a crucial way.

References in corpus (5)

• Edge Universality of Beta Ensembles
• Universality in Numerical Computations with Random Data. Case Studies
• Near-extreme eigenvalues and the first gap of Hermitian random matrices
• Typical versus averaged overlap distribution in Spin-Glasses : Evidence for the droplet scaling theory
• The Eigenvector Moment Flow and local Quantum Unique Ergodicity

Cited by in corpus (3)

• Some Open Problems in Random Matrix Theory and the Theory of Integrable Systems. II
• Smoothed Analysis for the Conjugate Gradient Algorithm
• Universality for eigenvalue algorithms on sample covariance matrices