We describe algorithms for computing eigenpairs (eigenvalue--eigenvector) of a complex @math matrix @math . These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.
 We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an @math n×n Hermitian matrix @math A, the algorithm returns, almost surely, a pair @math (?,v) which approximates, in a very strong sense, an eigenpair of @math 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 @math A, is @math O(n6), 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. A unitarily invariant projective framework is introduced to analyze the complexity of path-following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill-posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale’s ( )-theorem is proven. The main result of this paper bounds the complexity of path-following methods in terms of the length of the path in the condition metric.