THE COMPLEXITY OF THE ALGEBRAIC EIGENPROBLEM

VICTOR Y. PAN ZHAO Q. CHEN AILONG ZHENG

Abstract. 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.