Volume 7, pp. 141-162, 1998.

Truncated QZ methods for large scale generalized eigenvalue problems

D. C. Sorensen

Abstract

This paper presents three methods for the large scale generalized eigenvalue problem $\mathbf{A}\mathbf{x}=\mathbf{B}\mathbf{x}\lambda$. 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 ($\mathbf{A},\mathbf{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 methods 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 ($\mathbf{A},\mathbf{B}$). Preliminary computational experience is presented to compare the three new methods.

Full Text (PDF) [169 KB], BibTeX

Key words

Generalized eigenvalue problem, Krylov projection methods, Arnoldi method, Lanczos method, QZ method, block methods, preconditioning, implicit restarting.

AMS subject classifications

65F15, 65G05.

ETNA articles which cite this article

Vol. 23 (2006), pp. 5-14 Alexander Malyshev and Miloud Sadkane: Condition numbers of the Krylov bases and spaces associated with the truncated QZ iteration