A stable, polynomial-time algorithm for the eigenpair problem

被引：14

作者：

Armentano, Diego ^{[1
]}

Beltran, Carlos ^{[2
]}

Buergisser, Peter ^{[3
]}

Cucker, Felipe ^{[4
]}

Shub, Michael ^{[5
]}

机构：

[1] Univ Republica, Montevideo, Uruguay

[2] Univ Cantabria, Santander, Spain

[3] Tech Univ Berlin, Berlin, Germany

[4] City Univ Hong Kong, Hong Kong, Hong Kong, Peoples R China

[5] CUNY, New York, NY 10021 USA

来源：

JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY | 2018年 / 20卷 / 06期

关键词：

Eigenvalue computations; homotopy methods; EIGENVALUE PROBLEMS; BEZOUTS THEOREM; HOMOTOPY METHOD; COMPLEXITY;

D O I：

10.4171/JEMS/789

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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

引用

页码：1375 / 1437

页数：63

共 58 条

[1] Probabilistic Analysis of the Grassmann Condition Number [J].