A STABLE POLYNOMIAL-TIME ALGORITHM FOR THE EIGENPAIR PROBLEM
There are well known methods to compute the eigenvalues and eigenvectors of any given matrix, but when it comes to the theoretical complexity analysis of these methods much less is known!
By carefully studying the condition number for the EVP, we design a homotopy method for this problem and prove that it has average polynomial running time.
Based on a paper by Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker and Michael Shub.
Published in Journal of the European Mathematical Society
