The EMS Publishing House is now EMS Press and has its new home at

Please find all EMS Press journals and articles on the new platform.

Journal of the European Mathematical Society

Full-Text PDF (415 KB) | Metadata | Table of Contents | JEMS summary
Volume 20, Issue 6, 2018, pp. 1375–1437
DOI: 10.4171/JEMS/789

Published online: 2018-04-16

A stable, polynomial-time algorithm for the eigenpair problem

Diego Armentano, Carlos Beltrán[1], Peter Bürgisser[2], Felipe Cucker[3] and Michael Shub[4]

(1) Universidad de Cantabria, Santander, Spain
(2) Technische Universität Berlin, Germany
(3) City University of Hong Kong, Kowloon Tong, Hong Kong
(4) City University of New York, USA

We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) 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.

A short professional video explaining the article can be found here: A stable, polynomial-time algorithm for the eigenpair problem.

Keywords: Eigenvalue computations, homotopy methods

Armentano Diego, Beltrán Carlos, Bürgisser Peter, Cucker Felipe, Shub Michael: A stable, polynomial-time algorithm for the eigenpair problem. J. Eur. Math. Soc. 20 (2018), 1375-1437. doi: 10.4171/JEMS/789