A stable, polynomial-time algorithm for the eigenpair problem

  • Diego Armentano

    Universidad de la República, Montevideo, Uruguay
  • Carlos Beltrán

    Universidad de Cantabria, Santander, Spain
  • Peter Bürgisser

    Technische Universität Berlin, Germany
  • Felipe Cucker

    City University of Hong Kong, Kowloon Tong, Hong Kong
  • Michael Shub

    City University of New York, USA

Abstract

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

Cite this article

Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, Michael Shub, A stable, polynomial-time algorithm for the eigenpair problem. J. Eur. Math. Soc. 20 (2018), no. 6, pp. 1375–1437

DOI 10.4171/JEMS/789