Next: Preconditioned Lanczos Methods Up: Preconditioned Eigensolvers   A. Knyazev Previous: Preconditioned Shifted Power Method   Contents   Index

## Preconditioned Steepest Ascent/Descent Methods

These methods are similar to Algorithm 11.5 in the previous subsection, but the shifts are chosen in the process of iterations and do not require knowledge of any bounds. Historically, preconditioned steepest descent/ascent methods for eigenproblems were suggested earlier (see [225,393,365]) than the power method with an a priori choice of the shift of the previous subsection.

Here, we present the single-vector version of the preconditioned steepest ascent for the pencil in Algorithm 11.6. For , , the method becomes a steepest descent method for .

We note that the shift can be determined with the Rayleigh-Ritz method for the pencil on the trial subspace . As the trial space is two-dimensional, the projection problem can be solved as a quadratic equation. Thus, one can derive explicit formulas for as roots of a quadratic polynomial.

By construction, the steepest ascent (descent) method provides maximization (minimization) of the Rayleigh quotient on every iteration as compared with the corresponding iterative Algorithm 11.5. Therefore, the convergence results from the previous section can be applied without any changes, and similar observations can be made.

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

 Item Storage Residual -vector Approximate eigenvector -vector Temporary vectors 3-5 -vectors

 Action Major cost Rayleigh-Ritz method dots and matrix-vector products Residual matrix-vector products, update Preconditioned residual Depends on preconditioner Approximate eigenvector update

The main advantages of the preconditioned steepest descent/ascent method are its relative simplicity and a minimal cost of every iteration compared to other preconditioned eigensolvers considered below. Using the Rayleigh-Ritz method instead of an a priori chosen shift does not require knowledge of any bounds. On the negative side, every iteration may cost about twice that of Algorithm 11.5. Though convergence is usually better than that of Algorithm 11.5 it is still worse than linear convergence of other preconditioned eigensolvers we consider below.

Next: Preconditioned Lanczos Methods Up: Preconditioned Eigensolvers   A. Knyazev Previous: Preconditioned Shifted Power Method   Contents   Index
Susan Blackford 2000-11-20