A stable, polynomial-time algorithm for the eigenpair problem (Q1644000)

This paper has 62 pages and develops an algorithm that computes all eigenvalue-eigenvector pairs of a complex \(n\) by \(n\) matrix \(A\) if \(A\) does not have repeated eigenvalues nor a non-trivial Jordan structure. For matrices with Gaussian random entries the method is proven numerically stable, strongly accurate and polynomial-time efficient. It translates the matrix eigenproblem to an initial value problem using the matrix eigenvalue-eigenvector equation for \(A\) and employs a path-following homotopy to approximate eigenpairs with the above three qualities. The method then computes matrix eigenpairs to the desired accuracy via an ODE solver. For such random entry matrices the theoretical operations count is of order \(O(n^9)\). This greatly exceeds the \(O(n^3)\) OP count of Francis and other QR algorithms which do not satisfy all three desired qualities. Numerical tests with \(n \leq 64\) matrices indicate that a more realistic average cost of this extensive method may be around \(O(n^7)\). The paper extends many of our well known definitions of matrix conditioning and algorithm stability. It introduces varieties and metrics for this numerical problem and proves detailed stepsize and convergence estimates for the homotopy based computational method. Its aim is to solve the old and open quandry of achieving all three: numerical stability, (near) global, and quick convergence for matrix eigen-computations.