Volume 40, pp. 17-35, 2013.

An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil

Raf Vandebril and David S. Watkins

Abstract

Recently, an extension of the class of matrices admitting a Francis type of multishift $QR$ algorithm was proposed by the authors. These so-called condensed matrices admit a storage cost identical to that of the Hessenberg matrix and share all of the properties essential for the development of an effective implicit $QR$ type method. This article continues along this trajectory by discussing the generalized eigenvalue problem. The novelty does not lie in the almost trivial extension of replacing the Hessenberg matrix in the pencil by a condensed matrix, but in the fact that both pencil matrices can be partially of condensed form. Again, the storage cost and crucial features of the Hessenberg-upper triangular pencil are retained, giving rise to an equally viable $QZ$-like method. The associated implicit algorithm also relies on bulge chasing and exhibits a sort of bulge hopping from one to the other matrix. This article presents the reduction to a condensed pencil form and an extension of the $QZ$ algorithm. Relationships between these new ideas and some known algorithms are also discussed.

Full Text (PDF) [337 KB], BibTeX

Key words

condensed matrices, generalized eigenvalues, $QZ$ algorithm, $QR$ algorithm, extended Krylov

AMS subject classifications

65F15, 15A18

ETNA articles which cite this article

Vol. 44 (2015), pp. 327-341 Jared L. Aurentz, Thomas Mach, Raf Vandebril, and David S. Watkins: Fast and stable unitary QR algorithm

Vol. 52 (2020), pp. 480-508 Daan Camps, Thomas Mach, Raf Vandebril, and David S. Watkins: On pole-swapping algorithms for the eigenvalue problem

< Back