An implicit QZ method for the application of a filter in the extended and rational Krylov method

Extended Krylov methods differ from classical Krylov methods in using also matrix inverses to build the Krylov subspace. Extended Krylov methods form a subclass of the rational Krylov methods and have proven to be useful in computing eigenvalues localized around the origin, ap- proximating particular matrix functions, or solving matrix equations. Restarting the iteration is generally required to limit the orthogonalization and storage costs. For standard Arnoldi, Fran- cisâ implicitly shifted QR algorithm can be used to efficiently execute QR steps on the matrix of recurrences, which is of Hessenberg form. The result is a new Hessenberg form matching a new Krylov subspace, having favorable convergence properties for the desired eigenvalues. The currently existing implicit restart approaches for rational Krylov and extended Krylov methods apply unstructured unitary transformations on the Hessenberg matrices. We observed that this is not only more expensive than exploiting structure, it also perturbs the Krylov spaces with loss of convergences of eigenvalues as a consequence. Our long term goal is to develop implicit restarting using unitary core transformations on a QR factorization of the recurrence matrices for rational Krylov. This paper presents a first step towards this goal, i.e., an implicit restart method for the extended Krylov method and a conversion from rational Krylov to extended Krylov so that filter- ing can be applied efficiently. This method acts directly, by means of unitary core transformations on a QR factorization of the recurrence matrices. In this manner, the structure in the recurrence matrices is preserved. The numerical experiments show the validity and increased accuracy of the new approach compared with existing methods.status: submitte