A novel, blocked algorithm for the reduction to Hessenberg-triangular form

Abstract

We present an alternative algorithm and implementation for the
Hessenberg-triangular reduction, an essential step in the QZ
algorithm for solving generalized eigenvalue problems. The
reduction step has a cubic computational complexity, and hence,
high-performance implementations are compulsory for keeping the
computing time under control. Our algorithm is of simple
mathematical nature and relies on the connection between
generalized and classical eigenvalue problems. Via system solving and
the classical reduction of a single matrix to Hessenberg form, we are
able to get a theoretically equivalent reduction to
Hessenberg-triangular form. As a result, we can perform most of the
computational work by relying on existing, highly efficient implementations,
which make extensive use of blocking. The accompanying error analysis
shows that preprocessing and iterative refinement can be
necessary to achieve accurate results. Numerical results show
competitiveness with existing implementations.