Next: Convergence Properties Up: Implicitly Restarted Lanczos Method Previous: Shift Selection   Contents   Index

Lanczos Method in GEMV Form

At each restart in Algorithm 4.7 we have a -step Lanczos factorization

or, for a starting vector . Algorithm 4.8 gives a template for applying additional Lanczos steps to extend this to an -step Lanczos factorization

We will now describe some implementation details, referring to the respective phases in Algorithm 4.8.

(2)
If started from scratch () take as a starting vector. Ideally, for eigenvalue calculations, one should attempt to construct a that is dominant in eigenvector directions of interest. In the absence of any other considerations, a random vector is a reasonable choice.

(3)
Normalize to get the new basis vector . The norm has already been computed at step (7) for the previous .

(5)
This is the Lanczos three-term recurrence step to orthogonalize with respect to the two most recent columns of . It is organized in modified Gram-Schmidt form.

(7)
The sequence of statements in this if clause assure that the new residual direction is numerically orthogonal to the previously computed directions, i.e., to all of the columns of . The parameter must be specified ( ). The test asks the question, Is nearly in the space that already has been constructed?" The ratio , where is the angle that the vector makes with the range space of . A larger value of is a more stringent orthogonality requirement. With , the algorithm reverts to the standard Lanczos process without reorthogonalization. One step of this correction may not be sufficient and it should be implemented as an iteration with the test for subsequent corrections being ; see the discussion in [96]. If a suitable has not been generated after a fixed number of attempts (say five), then should be set to zero and a randomly generated vector should be orthogonalized against the basis and put in place of to continue the factorization. We suggest setting .

It is well known that the classical three-term Lanczos scheme will fail to produce orthogonal vectors precisely when a Ritz value (approximate eigenvalue) converges to an eigenvalue of . To remedy this, we have included an iterative refinement technique which maintains orthogonality to full working precision at a very reasonable cost. The special situation imposed by implicit restart makes this modification essential for obtaining accurate eigenvalues and numerically orthogonal eigenvectors. The implicit restart mechanism will be less effective and may even fail if numerical orthogonality is not maintained.

Next: Convergence Properties Up: Implicitly Restarted Lanczos Method Previous: Shift Selection   Contents   Index
Susan Blackford 2000-11-20