TRUNCATED QZ METHODS FOR LARGE SCALE GENERALIZED EIGENVALUE PROBLEMS

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 eigenvalue problem. These two meth-ods require the accurate solution 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. 65F15, 65G05