Deflating invariant subspaces for rank structured pencils

Abstract

It is known that executing a perfect shifted $QR$ step via the implicit $QR$ algorithm may not result in a deflation of the perfect shift. Typically, several steps are required before deflation actually takes place. This deficiency can be remedied by determining the similarity transformation via the associated eigenvector. Similar techniques have been deduced for the $QZ$ algorithm and for the rational $QZ$ algorithm. In this paper, we present a similar approach for executing a perfect shifted $QZ$ step on a general rank structured pencil instead of a specific rank structured one, e.g., a Hessenberg-Hessenberg pencil. For this, we rely on the rank structures present in the transformed matrices. A theoretical framework is presented for dealing with general rank structured pencils and deflating subspaces. We present the corresponding algorithm allowing to deflate simultaneously a block of eigenvalues rather than a single one. We define the level-$\rho$ poles and show that these poles are maintained executing the deflating algorithm. Numerical experiments illustrate the robustness of the presented approach showing the importance of using the improved scaled residual approach.