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

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
Online access to the full text of Journal of the European Mathematical Society is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
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