Naslov
A Householder-based algorithm for Hessenberg-triangular reduction

Autori
Bujanović, Zvonimir ; Karlsson, Lars ; Kressner, Daniel

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Skup
ApplMath18, Ninth conference on applied mathematics and scientific computing

Mjesto i datum
Šibenik, Hrvatska, 17.09.2018. - 20.09.2018

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Nije recenziran

Ključne riječi
Hessenberg-triangular reduction ; Householder reflectors ; iterative refinement

Sažetak
Reducing the matrix pair $(A, B)$ to Hessenberg-triangular form is an important and time-con\-su\-ming 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, 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. 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA