A Randomized Homotopy for the Hermitian Eigenpair Problem
We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an \(n\times n\) Hermitian matrix \(A\), the algorithm returns, almost surely, a pair \((\lambda ,v)\) which approximates, in a very strong sense, an eigenpair of \(A\). We prove that the expected cost of this algorithm, where the expectation is both over the random choices of the algorithm and a probability distribution on the input matrix \(A\), is \(\mathcal{{O}}(n^6)\), that is, cubic on the input size. Our result relies on a cost assumption for some pseudorandom number generators whose rationale is argued by us.
eigenpair computation homotopy methods complexity analysis 65f15