umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimally Packed Chains of Bulges in Multishift QR Algorithms
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4675-7434
2014 (Engelska)Ingår i: ACM Transactions on Mathematical Software, ISSN 0098-3500, E-ISSN 1557-7295, Vol. 40, nr 2, s. 12-Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2014. Vol. 40, nr 2, s. 12-
Nyckelord [en]
Algorithms, Performance, Multishift QR algorithms, implicit shifts, level 3 BLAS
Nationell ämneskategori
Data- och informationsvetenskap Matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-88415DOI: 10.1145/2559986ISI: 000333653400004OAI: oai:DiVA.org:umu-88415DiVA, id: diva2:715949
Tillgänglig från: 2014-05-07 Skapad: 2014-05-05 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Karlsson, Lars

Sök vidare i DiVA

Av författaren/redaktören
Karlsson, Lars
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
ACM Transactions on Mathematical Software
Data- och informationsvetenskapMatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 158 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf