Theoretical and Computable Optimal Subspace Expansions for Matrix Eigenvalue Problems

Consider the optimal subspace expansion problem for the matrix eigenvalue problem $Ax=\lambda x$: Which vector $w$ in the current subspace $\mathcal{V}$, after multiplied by $A$, provides an optimal subspace expansion for approximating a desired eigenvector $x$ in the sense that $x$ has the smallest angle with the expanded subspace ${\mathcal{V}}_w=\mathcal{V}+\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{Aw\}$, i.e., $w_{opt}=\arg {\max }_{w\in \mathcal{V}}\cos \mathrm{\angle }({\mathcal{V}}_w,x)$? This problem is important as many iterative methods construct nested subspaces that successively expand $\mathcal{V}$ to ${\mathcal{V}}_w$. An expression of $w_{opt}$ by Ye (Linear Algebra Appl., 428 (2008), pp. 911–918) for $A$ general, but it could not be exploited to construct a computable (nearly) optimally expanded subspace. He turns to deriving a maximization characterization of $\cos \mathrm{\angle }({\mathcal{V}}_w,x)$ for a {\em given} $w\in $\mathcal{V}$$when$A$ is Hermitian. We generalize Ye’s maximization characterization to the general case and find its maximizer. Our main contributions consist of explicit expressions of $w_{opt}$, $(I-P_V)A{w}_{opt}$ and the optimally expanded subspace ${\mathcal{V}}_{w_{opt}}$ for $A$ general, where $P_V$ is the orthogonal projector onto $\mathcal{V}$. These results are fully exploited to obtain computable optimally expanded subspaces within the framework of the standard, harmonic, refined, and refined harmonic Rayleigh–Ritz methods. We show how to efficiently implement the proposed subspace expansion approaches. Numerical experiments demonstrate the effectiveness of our computable optimal expansions.