A stable, polynomial-time algorithm for the eigenpair problem
For numerical linear algebra researchers, it solves a theoretical open problem about the existence of stable polynomial-time eigenpair algorithms.
The paper presents the first stable, polynomial-time algorithm for computing eigenpairs of complex matrices, resolving a long-standing open problem in numerical linear algebra, though it does not outperform existing practical algorithms.
We describe algorithms for computing eigenpairs (eigenvalue--eigenvector) of a complex $n\times n$ matrix $A$. 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.