Block subspace expansions for eigenvalues and eigenvectors approximation

Abstract

Let A ∈ Cn×n be an Hermitian matrix with eigenvalues λ1 ≥ . . . ≥ λn. Assume that λd > λd+1 for some d ≥ 1 and let X ⊂ Cn be the simple A-invariant d-dimensional subspace spanned by the eigenvectors of A associated with the biggest eigenvalues. Given an initial subspace V ⊂ Cn with dim V = r ≥ d, we search for expansions V + A(W0), where W0 ⊂ V is such that dimW0 ≤ d and such that the expanded subspace is closer to X than V. We show that there exist optimal W0, in the sense that θi(X, V + A(W0)) ≤ θi(V + A(W)) for every W ⊂ V with dimW ≤ d, where θi(X, S) denotes the i-th principal angle between X and S, for 1 ≤ i ≤ d ≤ dim S. We relate these optimal expansions to block Krylov subspaces and show that, under these conditions on A and X, the corresponding iterative sequence of subspaces constructed in this way approximates X arbitrarily well. We further introduce computable versions of this construction and compute several numerical examples to test their performance.