Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 1102813

A Householder-based algorithm for Hessenberg-triangular reduction


Bujanović, Zvonimir; Karlsson, Lars; Kressner, Daniel
A Householder-based algorithm for Hessenberg-triangular reduction // NASCA 2018
Kalamata, Grčka, 2018. str. 51-51 (predavanje, nije recenziran, sažetak, znanstveni)


CROSBI ID: 1102813 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

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
NASCA 2018

Mjesto i datum
Kalamata, Grčka, 02-06.07.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-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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika



POVEZANOST RADA


Projekti:
HRZZ-IP-2013-11-9345 - Matematičko modeliranje, analiza i računanje s primjenama na kompleksne mehaničke sustave (MMACACMS) (Drmač, Zlatko, HRZZ - 2013-11) ( POIROT)

Ustanove:
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb,
Prirodoslovno-matematički fakultet, Zagreb

Profili:

Avatar Url Daniel Kressner (autor)

Avatar Url Zvonimir Bujanović (autor)

Citiraj ovu publikaciju

Bujanović, Zvonimir; Karlsson, Lars; Kressner, Daniel
A Householder-based algorithm for Hessenberg-triangular reduction // NASCA 2018
Kalamata, Grčka, 2018. str. 51-51 (predavanje, nije recenziran, sažetak, znanstveni)
Bujanović, Z., Karlsson, L. & Kressner, D. (2018) A Householder-based algorithm for Hessenberg-triangular reduction. U: NASCA 2018.
@article{article, year = {2018}, pages = {51-51}, keywords = {Hessenberg-triangular reduction, Householder reflectors, iterative refinement}, title = {A Householder-based algorithm for Hessenberg-triangular reduction}, keyword = {Hessenberg-triangular reduction, Householder reflectors, iterative refinement}, publisherplace = {Kalamata, Gr\v{c}ka} }
@article{article, year = {2018}, pages = {51-51}, keywords = {Hessenberg-triangular reduction, Householder reflectors, iterative refinement}, title = {A Householder-based algorithm for Hessenberg-triangular reduction}, keyword = {Hessenberg-triangular reduction, Householder reflectors, iterative refinement}, publisherplace = {Kalamata, Gr\v{c}ka} }




Contrast
Increase Font
Decrease Font
Dyslexic Font