engleski

A Householder-based algorithm for Hessenberg-triangular reduction

Reducing the matrix pair $(A, B)$ to Hessenberg-triangular form is an important and time-consuming preprocessing step when computing eigenvalues and eigenvectors of the pencil $A - \lambda B$ by the QZ-algorithm. Current state-of-the-art algorithms for this reduction are based on Givens rotations, which limits the possibility of using efficient level 3 BLAS operations, as well as parallelization potential on modern CPUs. Both of these issues remain even with partial accumulation of Givens rotations \cite{; ; Kagstrom2008}; ; , implemented, e.g., in LAPACK. In this talk we present a novel approach for computing the Hessenberg-triangular reduction, which is based on using Householder reflectors. The key element in the new algorithm is the lesser known ability of Householder reflectors to zero-out elements in a matrix column even when applied from the right side of the matrix \cite{; ; Watkins2000, Kagstrom2006}; ; . The performance of the new reduction algorithm is boosted by blocking and other optimization techniques, all of which permit efficient use of level 3 BLAS operations. We also discuss measures necessary for ensuring numerical stability of the algorithm. While the development of a parallel version is future work, numerical experiments already show benefits of the Householder-based approach compared to Givens rotations in the multicore computing environment. This is joint work with Lars Karlsson and Daniel Kressner.

Hessenberg-triangular reduction ; Householder reflectors ; iterative refinement

nije evidentirano