CRPC-TR98775						May 1998

Title: Deflation for Implicitly Restarted Arnoldi Methods

Author: D.C. Sorensen

Submitted September 1998; Available as Rice CAAM TR98-12

Abstract:
The implicitly restarted Arnoldi method (IRAM) is an effective technique 
for computing a selected subset of the eigenvalues and corresponding 
eigenvectors of a large matrix A. However, the performance of this method 
can be improved considerably with the introduction of appropriate 
deflation schemes to isolate approximate invariant subspaces associated 
with converged Ritz values. These deflation strategies make it possible 
to compute multiple or clustered eigenvalues with a single vector 
implicit restart method.

It is of particular interest to provide schemes that can deflate with 
user specified relative error tolerances Ed that are considerably greater 
than working precision Em. The primary contribution of this paper is to 
develop efficient and numberically stable schemes for this purpose. Two 
forms of deflation are presented. The first, a locking operation, 
decouples converged Ritz values and the associated invariant subspace 
from the active part of the IRAM iteration. The second, a purging 
operation, removes unwanted but converged Ritz pairs. Convergence of the 
IRAM iteration is improved and a reduction in computational effort is 
also achieved.

Key words: eigenvalues, deflation, implicit restarting, Krylov projection 
methods, Arnoldi method, Lanczos method

AMS subject classifications: Primary 65F15, Secondary 65G05

------------------------------------------------------------------------------
D.C. Sorensen
sorensen@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University