Krylov Subspaces and Projection Methods

The methods that underly the ARPACK software are derived from a class of algorithms called Krylov  subspace projection methods.    These methods take full advantage of the intricate structure of   the sequence of vectors naturally produced by the power method.

An examination of the behavior of the sequence of vectors produced by the power method suggests that the successive vectors may contain considerable information along eigenvector directions corresponding to eigenvalues other than the one with largest magnitude. The expansion coefficients of the vectors in the sequence evolve in a very structured way. Therefore, linear combinations of the these vectors can be constructed to enhance convergence to additional eigenvectors. A single vector power iteration simply ignores this additional information, but more sophisticated techniques may be employed to extract it.

If one hopes to obtain additional information through various linear combinations of the power sequence, it is natural to formally consider the Krylov subspace 

and to attempt to formulate the best possible approximations to eigenvectors from this subspace.

It is reasonable to construct approximate eigenpairs from this subspace by imposing a Galerkin condition : A vector is called a Ritz vector   with corresponding Ritz value   if the Galerkin condition

is satisfied. There are some immediate consequences of this definition: Let be a matrix whose columns form an orthonormal basis for Let denote the related orthogonal projector  onto and define where It can be shown that

Lemma 13934

For the quantities defined above:

1.

is a Ritz-pair if and only if with .

2.

for all such that .

3.

The Ritz-pairs and the minimum value are independent of the choice of orthonormal basis

These facts are actually valid for any k dimensional subspace in place of Additional useful properties may be derived as consequences of the fact that every is of the form for some polynomial of degree less than k. A thorough discussion is given by Saad in [40] and in his earlier papers. These facts have important algorithmic consequences. In particular, it may be shown that is an invariant subspace for ${\bf A}$ if and only if the starting vector is a linear combination of vectors spanning an invariant subspace of   An important example of this is to put where is a partial Schur decomposition  of

There is some algorithmic motivation to seek a convenient orthonormal basis that will provide a means to successively construct these basis vectors. It is possible to construct a unitary using standard Householder transformations such that and is upper Hessenberg with non-negative subdiagonal elements. It is also possible to show that in this basis,

with implied by the projection property and .

If it is possible to obtain a as a linear combination of k eigenvectors of ${\bf A}$, the first observation implies that and is an orthonormal basis for an invariant subspace of ${\bf A}$. Hence, the Ritz values are eigenvalues and corresponding Ritz vectors are eigenvectors for ${\bf A}$. The second observation leads to the Lanczos/Arnoldi process [2,20].