Next: Preconditioned Steepest Ascent/Descent Methods Up: Preconditioned Eigensolvers   A. Knyazev Previous: General Framework of Preconditioning   Contents   Index

## Preconditioned Shifted Power Method

The preconditioned power method with a shift is the simplest preconditioned iterative method. It can only find the smallest (or largest, for a different shift) eigenvalue and the corresponding eigenvector.

We present the single-vector version of the method for the pencil in Algorithm 11.5. On the output, and approximate the largest eigenvalue and its corresponding eigenvector.

We note that the shift requires knowledge of , or its estimate from below. If is nonnegative definite, then may simply be replaced with .

The standard arguments, based on the eigendecomposition of for the pencil , do not allow us to show that the power method converges, as eigenvectors in the eigendecomposition are not necessarily eigenvectors of the iteration operator. This makes convergence theory quite tricky. D'yakonov and his colleagues [150,146,147] obtained explicit estimates of linear convergence for iterative Algorithm 11.5 using assumption (11.9). Somewhat simplified (see [264,265,268]), the convergence rate estimate for Algorithm 11.5 can be written as

 (283)

under the assumption that

The estimate shows that the convergence is (at least) linear. Note that condition numbers of and do not appear in the estimate.

Similar results can be obtained if for some holds [147].

In numerical experiments, Algorithm 11.5 usually converges to for a random initial guess. When , the sequence needs to pass eigenvectors, which are saddle points of the Rayleigh quotient, to reach . The convergence may slow down, in principle, near every saddle point. For a general preconditioner , it is hard to predict whether this can happen for a given initial guess .

We have collected the dominant costs per iteration for Algorithm 11.5 in terms of storage and floating point operations respectively, in the following two tables.

 Item Storage Residual -vector Approximate eigenvector -vector Temporary vectors 1-2 -vectors

 Action Major cost Rayleigh quotient dots Residual matrix-vector products Preconditioned residual Depends on preconditioner Approximate eigenvector update

The main advantage of the preconditioned shifted power method is, of course, its algorithmic simplicity and the low costs per iteration. Using an a priori chosen shift provides the total control of the iterative method. The method is very stable and robust. A solid convergence theory exists.

The need of bounds for and to calculate the shift is a clear disadvantage. Also, other preconditioned eigensolvers we consider below converge linearly as well, but typically with a better rate.

Next: Preconditioned Steepest Ascent/Descent Methods Up: Preconditioned Eigensolvers   A. Knyazev Previous: General Framework of Preconditioning   Contents   Index
Susan Blackford 2000-11-20