Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A Householder-Based Algorithm For Hessenberg-Triangular Reduction
 
research article

A Householder-Based Algorithm For Hessenberg-Triangular Reduction

Bujanovic, Zvonimir  
•
Karlsson, Lars
•
Kressner, Daniel  
January 1, 2018
Siam Journal On Matrix Analysis And Applications

The QZ algorithm for computing eigenvalues and eigenvectors of a matrix pencil A - lambda B requires that the matrices first be reduced to Hessenberg-triangular (HT) form. The current method of choice for HT reduction relies entirely on Givens rotations regrouped and accumulated into small dense matrices which are subsequently applied using matrix multiplication routines. A nonvanishing fraction of the total flop-count must nevertheless still be performed as sequences of overlapping Givens rotations alternately applied from the left and from the right. The many data dependencies associated with this computational pattern leads to inefficient use of the processor and poor scalability. In this paper, we therefore introduce a fundamentally different approach that relies entirely on (large) Householder reflectors partially accumulated into block reflectors, by using (compact) WY representations. Even though the new algorithm requires more floating point operations than the state-of-the-art algorithm, extensive experiments on both real and synthetic data indicate that it is still competitive, even in a sequential setting. The new algorithm is conjectured to have better parallel scalability, an idea which is partially supported by early small-scale experiments using multithreaded BLAS. The design and evaluation of a parallel formulation is future work.

  • Details
  • Metrics
Type
research article
DOI
10.1137/17M1153637
Web of Science ID

WOS:000453716400010

Author(s)
Bujanovic, Zvonimir  
Karlsson, Lars
Kressner, Daniel  
Date Issued

2018-01-01

Publisher

SIAM PUBLICATIONS

Published in
Siam Journal On Matrix Analysis And Applications
Volume

39

Issue

3

Start page

1270

End page

1294

Subjects

Mathematics, Applied

•

Mathematics

•

hessenberg-triangular reduction

•

householder reflectors

•

iterative refinement

•

qr algorithm

•

qz algorithm

•

form

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MATHICSE  
ANCHP  
Available on Infoscience
January 3, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/153322
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés