Average polynomial time for eigenvector computations
arXiv:1410.2179
Originality Highly original
AI Analysis
It provides the first average polynomial-time algorithms for eigenvector computations on a natural random matrix ensemble, addressing a long-standing open problem in numerical linear algebra.
The paper presents two algorithms that compute eigenvalues and eigenvectors of Gaussian random matrices with complex entries, achieving average polynomial time complexity with probability 1.
We describe two algorithms for the eigenvalue, eigenvector problem which, on input a Gaussian matrix with complex entries, finish with probability 1 and in average polynomial time.