Next: Software Availability Up: Implicitly Restarted Arnoldi Method Previous: Locking and Purging in   Contents   Index

## Eigenvector Computation with Spectral Transformation

The SI was introduced in §3.3. Specifically, we use the matrix

in place of and rely on the fact that

to recover eigenvalues of the original matrix. The Arnoldi method is extremely effective when used in conjunction with SI. Convergence to eigenvectors corresponding to the eigenvalues of that are nearest to is generally very rapid. Hence, this approach should be used whenever it is possible to solve linear systems efficiently with as the coefficient matrix.

When a spectral transformation is used, additional considerations should be made with respect to stopping criteria to take advantage of the special nature of the transformed operator . Moreover, the quality of the approximate eigenvectors can be improved significantly with a minor amount of postprocessing. In order to compute eigenvalues of near to we will compute the eigenvalues of that are of largest magnitude. It is not really necessary for to be extremely close to a desired eigenvalue. However, for the following discussion it is worth keeping in mind that in practice, it is typical to take near to desired eigenvalues, and hence it is typical for to hold.

Let with , where . Since

 (129)

it follows that is the norm of the residual . If , where is a user-specified tolerance, then according to (7.17), and are an exact eigenpair for a matrix near . However, we are really interested in eigenvalue-eigenvector approximations for the original matrix .

A simple rearrangement of (7.23) gives

 (130)

and this is the residual of the computed eigenpair for the matrix . However, with a minor amount of additional arithmetic, the quality of the eigenvector can be improved and the corresponding residual norm can be reduced significantly.

Adding and subtracting on the right-hand side of (7.24) and rearranging terms will result in

 (131)

where . In the case , we see that will be a much better approximate eigenvector than . Moreover, if is large relative to , then the potential magnification of error due to the term is avoided.

A heuristic argument further supports the use of instead of . From (7.23) it follows that

 (132)

and hence is the (normalized) vector that would result if we performed one step of inverse iteration with on .

This vector has not yet been scaled to have unit norm. However, , so the error bound will decrease after is normalized. Moreover, if , then the floating point computation of the norm will already result in without any rescaling.

From (7.23), the residual is orthogonal to the Krylov space spanned by the columns of . However, this Galerkin condition is lost upon transforming the computed eigenpair to the original system, regardless of whether we use or . This is because is not the Rayleigh quotient associated with or . However, from (7.25)

 (133)

In other words, the approximate eigenvalue is nearly a Rayleigh quotient for when the vector is used as the approximate eigenvector. In fact, will be within roundoff level of being a Rayleigh quotient when .

On the other hand, from (7.24) we deduce that

 (134)

is the error in using as a Rayleigh quotient for when is used.

Equations (7.25) and (7.27) imply that the vector is a better approximation than to the eigenvector associated with the approximate eigenvalue provided that is greater than 1. Moreover, when , only a moderately small Ritz estimate is needed to achieve an acceptably small direct residual and Rayleigh quotient error. If the is near the desired eigenvalues, then these eigenvalues are mapped by to large eigenvalues and typically .

The above analysis is based on that given by Ericsson and Ruhe [162] for the generalized symmetric definite eigenvalue problem.

Next: Software Availability Up: Implicitly Restarted Arnoldi Method Previous: Locking and Purging in   Contents   Index
Susan Blackford 2000-11-20