Implicit double shift QR-algorithm for companion matrices

• Published in: Numerische Mathematik 2010-08, Vol.116 (2), p.177-212
• Main Authors: Van Barel, Marc, Vandebril, Raf, Van Dooren, Paul, Frederix, Katrijn
• Format: Article
• Language: English
• Subjects: Combinatorics; Combinatorics. Ordered structures; Designs and configurations; Exact sciences and technology; Mathematical and Computational Engineering; Mathematical and Computational Physics; Mathematical Methods in Physics; Mathematics; Mathematics and Statistics; Nonlinear algebraic and transcendental equations; Numerical Analysis; Numerical analysis. Scientific computation; Numerical and Computational Physics; Numerical linear algebra; Sciences and techniques of general use; Simulation; Theoretical
• ISSN: 0029-599X; 0945-3245
• DOI: 10.1007/s00211-010-0302-y

In this paper an implicit (double) shifted QR -method for computing the eigenvalues of companion and fellow matrices will be presented. Companion and fellow matrices are Hessenberg matrices, that can be decomposed into the sum of a unitary and a rank 1 matrix. The Hessenberg, the unitary as well as the rank 1 structures are preserved under a step of the QR -method. This makes these matrices suitable for the design of a fast QR -method. Several techniques already exist for performing a QR -step. The implementation of these methods is highly dependent on the representation used. Unfortunately for most of the methods compression is needed since one is not able to maintain all three, unitary, Hessenberg and rank 1 structures. In this manuscript an implicit algorithm will be designed for performing a step of the QR -method on the companion or fellow matrix based on a new representation consisting of Givens transformations. Moreover, no compression is needed as the specific representation of the involved matrices is maintained. Finally, also a double shift version of the implicit method is presented.