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.

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