The Complexity of the Algebraic Eigenproblem
Victor Y. Pan, Zhao Q. Chen, and Ailong Zheng
The eigenproblem for an $n$-by-$n$ matrix $A$ is the problem of the approximation (within a relative error bound $2^{-b})$ of all the eigenvalues of the matrix $A$ and computing the associated eigenspaces of all these eigenvalues. We show that the arithmetic complexity of this problem is bounded by $O(n^3)$ if $\log b=O(n)$. For generic matices $A$ the bound decreases dramatically. We reach up to (poly)logarithmic factors the optimal levels $O(M(n))$ fo $n$-by-$n$ generic matrices (where $M(n)$ is the arithmetic cost of $n$-by-$n$ matrix multiplication) and $O(n^2)$ for $n$-by-$n$ generic matrices of various classes of sparse and dense structured matrices, the latter ones include the classes of Toeplitz, Hankel, Toeplitz-like, Hankel-like, Vandermonde-like and Cauchy-like matrices.