The complexity of the matrix eigenproblem 论文

摘要

The eigenproblem for an n-by-n matrix A is the problem of the approximation (within a relative error bound 2-') 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(n3 + (nlog'n)log b). If the characteristic and minimum polynomials of the matrix A coincide with each other (which is the ca8e for generic matrices of all classes of general and special matrices that we consider), then the latter deterministic cost bound can be replaced by the randomized bound O(K.a(2n) + n* + (n log'n) log b) where Ka(2n) denotes the cost of the computation of the 2n -1 vectors A'v, i = 1,. ,2n -1, maximized over all n-dimensional vectors v; Ka(2n) = O(M(n)logn), for M(n) = o(n2.3'6) denoting the arithmetic complexity of n x n matrix multiplication.