A Householder-based algorithm for Hessenberg-triangular reduction (CROSBI ID 698367)
Prilog sa skupa u zborniku | sažetak izlaganja sa skupa
Podaci o odgovornosti
Bujanović, Zvonimir ; Karlsson, Lars ; Kressner, Daniel
engleski
A Householder-based algorithm for Hessenberg-triangular reduction
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.
Hessenberg-triangular reduction ; Householder reflectors ; iterative refinement
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
19-19.
2018.
objavljeno
Podaci o matičnoj publikaciji
Podaci o skupu
ApplMath18, Ninth conference on applied mathematics and scientific computing
predavanje
17.09.2018-20.09.2018
Šibenik, Hrvatska