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. Optimally Packed Chains of Bulges in Multishift QR Algorithms
 
research article

Optimally Packed Chains of Bulges in Multishift QR Algorithms

Karlsson, Lars
•
Kressner, Daniel  
•
Lang, Bruno
2014
ACM Transactions on Mathematical Software

The QR algorithm is the method of choice for computing all eigenvalues of a dense nonsymmetric matrix A. After an initial reduction to Hessenberg form, a QR iteration can be viewed as chasing a small bulge from the top left to the bottom right corner along the subdiagonal of A. To increase data locality and create potential for parallelism, modern variants of the QR algorithm perform several iterations simultaneously, which amounts to chasing a chain of several bulges instead of a single bulge. To make effective use of level 3 BLAS, it is important to pack these bulges as tightly as possible within the chain. In this work, we show that the tightness of the packing in existing approaches is not optimal and can be increased. This directly translates into a reduced chain length by 33% compared to the state-of-the-art LAPACK implementation of the QR algorithm. To demonstrate the impact of our idea, we have modified the LAPACK implementation to make use of the optimal packing. Numerical experiments reveal a uniform reduction of the execution time, without affecting stability or robustness.

  • Details
  • Metrics
Type
research article
DOI
10.1145/2559986
Web of Science ID

WOS:000333653400004

Author(s)
Karlsson, Lars
Kressner, Daniel  
Lang, Bruno
Date Issued

2014

Publisher

Association for Computing Machinery

Published in
ACM Transactions on Mathematical Software
Volume

40

Issue

2

Start page

12

Subjects

Algorithms

•

Performance

•

Multishift QR algorithms

•

implicit shifts

•

level 3 BLAS

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ANCHP  
Available on Infoscience
May 2, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/103177
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