A stable, polynomial-time algorithm for the eigenpair problem

Abstract

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.

42 pages, 3 figures

References in corpus (2)

• Smoothed analysis of algorithms
• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric

Cited by in corpus (2)

• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
• Condition length and complexity for the solution of polynomial systems