Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithm 1019: A Task-based Multi-shift QR/QZ Algorithm with Aggressive Early Deflation
Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).ORCID iD: 0000-0002-3689-0899
2022 (English)In: ACM Transactions on Mathematical Software, ISSN 0098-3500, E-ISSN 1557-7295, Vol. 48, no 1, p. 1-36, article id 11Article in journal (Refereed) Published
Abstract [en]

The QR algorithm is one of the three phases in the process of computing the eigenvalues and the eigenvectors of a dense nonsymmetric matrix. This paper describes a task-based QR algorithm for reducing an upper Hessenberg matrix to real Schur form. The task-based algorithm also supports generalized eigenvalue problems (QZ algorithm) but this paper concentrates on the standard case. The task-based algorithm adopts previous algorithmic improvements, such as tightly-coupled multi-shifts and Aggressive Early Deflation (AED), and also incorporates several new ideas that significantly improve the performance. This includes, but is not limited to, the elimination of several synchronization points, the dynamic merging of previously separate computational steps, the shortening and the prioritization of the critical path, and experimental GPU support. The task-based implementation is demonstrated to be multiple times faster than multi-threaded LAPACK and ScaLAPACK in both single-node and multi-node configurations on two different machines based on Intel and AMD CPUs. The implementation is built on top of the StarPU runtime system and is part of the open-source StarNEig library.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2022. Vol. 48, no 1, p. 1-36, article id 11
Keywords [en]
aggressive early deflation, MPI, multi-shift, QR algorithm, QZ algorithm, real Schur form, distributed memory, StarPU, shared memory, task-based, Eigenvalue problem, GPU
National Category
Computer Sciences Computational Mathematics
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-190558DOI: 10.1145/3495005ISI: 000759468700012Scopus ID: 2-s2.0-85125191396OAI: oai:DiVA.org:umu-190558DiVA, id: diva2:1621413
Funder
EU, Horizon 2020, 671633eSSENCE - An eScience CollaborationSwedish Research Council, E0485301Available from: 2021-12-18 Created: 2021-12-18 Last updated: 2023-09-05Bibliographically approved

Open Access in DiVA

fulltext(1004 kB)199 downloads
File information
File name FULLTEXT02.pdfFile size 1004 kBChecksum SHA-512
3c8ec88ac5cb6b6315c629b8c383771698499c755515a8c0e70880081cbb51394df7a75c13d9cd0ce7090fcc720862ca6d5752ce6717867b7f98d07a4feea038
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Myllykoski, Mirko

Search in DiVA

By author/editor
Myllykoski, Mirko
By organisation
Department of Computing ScienceHigh Performance Computing Center North (HPC2N)
In the same journal
ACM Transactions on Mathematical Software
Computer SciencesComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 199 downloads
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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 708 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf