Chasing bulges or rotations? A metamorphosis of the QR-algorithm

The QR-algorithm is a renowned method for computing all eigenvalues of an arbitrary matrix. A preliminary unitary similarity transformation to Hessenberg form is indispensable for keeping the computational complexity of the subsequent QR-steps under control. When restraining computing time is the vital issue, we observe that the prominent role played by the Hessenberg matrix is sufficient but perhaps not necessary to fulfill this goal. In this paper, a whole new family of matrices, sharing the major qualities of Hessenberg matrices, will be put forward. This gives rise to the development of innovative implicit QR-type algorithms, pursuing rotations instead of bulges. The key idea is to benefit from the QR-factorization of the matrices involved. The prescribed order of rotations in the decomposition of the Q-factor uniquely characterizes several matrix types such as Hessenberg, inverse Hessenberg, and CMV matrices. Loosening the fixed ordering of these rotations provides us the class of matrices under consideration. Establishing a new implicit QR-type algorithm for these matrices requires a generalization of diverse well-established concepts. We consider the preliminary unitary similarity transformation, a proof of uniqueness of this reduction, an extension of the CMV -decomposition to a double Hessenberg factorization, and an explicit and implicit QR- type algorithm. A detailed complexity analysis illustrates the competitiveness of the novel method with the traditional Hessenberg approach. The numerical experiments show comparable accuracy for a wide variety of matrix types, but disclose an intriguing difference between the average number of iterations before deflation can be applied.status: publishe