A randomized homotopy for the Hermitian eigenpair problem (Q2340509)

The authors describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. For an \(n \times n\) Hermitian matrix \(A\), it returns a pair \((\lambda, v)\) that is a good approximation of an eigenpair of \(A\). The average cost of this algorithm -- over the random choices made by the algorithm and assuming \(A\) drawn from a Gaussian unitary ensemble [GUE(n)] distribution -- is bounded by \({\mathcal{O}}(n^6)\).