Next: Software Availability
Up: Implicitly Restarted Lanczos Method
Previous: Stability of .
  Contents
  Index
Although the basic deflation ideas of locking and purging are
conceptually straightforward, there are still a number of
implementation details and various strategies one might consider. In
the end, some ad-hoc decisions will have to be made. The deflation
strategy adopted here is somewhat conservative. However, the
performance appears to be quite reasonable in practice.
In [420], computational examples demonstrate that very crude
tolerances can be specified without missing multiple or clustered
eigenvalues.
The implementation details become quite involved and it is difficult to
convey the ideas by displaying code. Instead, we shall indicate the
main ideas of the strategy with a fairly high-level verbal description.
Implementation notes:
- (1)
- Initially, we work with an -step Lanczos factorization and
apply shifts per each implicit restart. Each time a Ritz value is
locked, it is advantageous to decrease the effective value of by
1. This allows the polynomial filter to have a larger relative
magnitude on the Ritz value that is most likely to converge next. (See
§4.5.4.) Of course, this must be limited to avoid
lowering the degree of the filter so much that it becomes ineffective.
If is the number of locked Ritz values, the IRLM iteration
takes place in columns
of , working within an
length Lanczos factorization. The effective value of becomes
and the effective value of becomes .
This has two important effects. The rate of convergence as described
in §4.5.4 is increased and the amount of work per
implicit restart is decreased.
- (2)
- One might also wish to purge all converged but unwanted Ritz pairs at this stage.
- (3)
- The purpose of introducing the random start vector here is to greatly increase
the likelihood of components in directions of wanted eigenvectors that have not
yet been found.
- (4)
- This ad-hoc stopping strategy is reasonable if there is no opportunity to factor .
However, there is no ultimate assurance that the wanted eigenvalues have
all been found (especially in the case of clustered or multiple eigenvalues).
If (or better yet ) can be factored into a
symmetric indefinite
factorization then convergence may be greatly
enhanced through spectral transformation
and one will have an inertia count available.
That will give a more reliable verification
that all wanted eigenvalues have been found.
See the discussion in §4.4.3.
Next: Software Availability
Up: Implicitly Restarted Lanczos Method
Previous: Stability of .
  Contents
  Index
Susan Blackford
2000-11-20