CRPC-TR98774						January 1998

Title: Truncated QZ Methods for Large Scale Generalized Eigenvalue Problems

Author: D.C. Sorensen

Submitted September 1998; Available as Rice CAAM TR98-01; To appear in 
"Electronic Transactions on Numerical Analysis"

Abstract:
This paper presents three methods for the large scale generalized 
eigenvalue problem Ax = Bx_. These methods are developed within a 
subspace projection framework as a truncation and modification of the 
QZ-algorithm for dense problems that is suitable for computing partial 
generalized Schur decompositions of the pair (A,B). A generalized partial 
reduction to condensed form is developed by analogy with the Arnoldi 
process. Then truncated forward and backward QZ iterations are introduced 
to derive generalizations of the Implicitly Restarted Arnoldi Method and 
the Truncated RQ method for the large scale generalized problem. These 
two methods require accurate solutions of linear systems at each step of 
the iteration. Relaxing these accuracy requirements forces us to 
introduce non-Krylov projection spaces that lead most naturally to block 
variants of the QZ iterations. A two-block method is developed that 
incorporates k approximate Newton corrections at each iteration. An 
important feature is the potential to utilize k matrix vector products 
for each access of the matrix pair (A,B). Preliminary computational 
experience is presented to compare the three new methods.

Key words: Generalized eigenvalue problem, Krylov projection methods, 
Arnoldi method, Lanczos method, QZ method, block methods, 
preconditioning, implicit restarting

AMS subject classifications: Primary 65F15, Secondary 65G05

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