Change search
ReferencesLink to record
Permanent link

Direct link
Optimally Packed Chains of Bulges in Multishift QR Algorithms
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2014 (English)In: ACM Transactions on Mathematical Software, ISSN 0098-3500, Vol. 40, no 2, 12- p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2014. Vol. 40, no 2, 12- p.
Keyword [en]
Algorithms, Performance, Multishift QR algorithms, implicit shifts, level 3 BLAS
National Category
Computer and Information Science Mathematics
URN: urn:nbn:se:umu:diva-88415DOI: 10.1145/2559986ISI: 000333653400004OAI: diva2:715949
Available from: 2014-05-07 Created: 2014-05-05 Last updated: 2014-05-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Karlsson, Lars
By organisation
Department of Computing Science
In the same journal
ACM Transactions on Mathematical Software
Computer and Information ScienceMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 53 hits
ReferencesLink to record
Permanent link

Direct link