Umeå universitets logga

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
Robust parallel eigenvector computation for the non-symmetric eigenvalue problem
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-8444-6303
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-9158-1941
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4675-7434
2020 (Engelska)Ingår i: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 100, artikel-id 102707Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A standard approach for computing eigenvectors of a non-symmetric matrix reduced to real Schur form relies on a variant of backward substitution. Backward substitution is prone to overflow. To avoid overflow, the LAPACK eigenvector routine DTREVC3 associates every eigenvector with a scaling factor and dynamically rescales an entire eigenvector during the backward substitution such that overflow cannot occur. When many eigenvectors are computed, DTREVC3 applies backward substitution successively for every eigenvector. This corresponds to level-2 BLAS operations and constitutes a bottleneck. This paper redesigns the backward substitution such that the entire computation is cast as tile operations (level-3 BLAS). By replacing LAPACK’s scaling factor with tile-local scaling factors, our solver decouples the tiles and sustains parallel scalability even when a lot of numerical scaling is necessary.

Ort, förlag, år, upplaga, sidor
Elsevier, 2020. Vol. 100, artikel-id 102707
Nyckelord [en]
Overflow protection, Eigenvectors, Real Schur form, Tiled algorithms
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-177534DOI: 10.1016/j.parco.2020.102707ISI: 000597159800001Scopus ID: 2-s2.0-85089018373OAI: oai:DiVA.org:umu-177534DiVA, id: diva2:1509213
Projekt
NLAFET
Anmärkning

Preprint version: http://umu.diva-portal.org/smash/record.jsf?pid=diva2%3A1396196&dswid=-7045

Tillgänglig från: 2020-12-11 Skapad: 2020-12-11 Senast uppdaterad: 2023-03-24Bibliografiskt granskad
Ingår i avhandling
1. Improving the efficiency of eigenvector-related computations
Öppna denna publikation i ny flik eller fönster >>Improving the efficiency of eigenvector-related computations
2021 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Alternativ titel[sv]
Förbättrad effektivitet för egenvektor-relaterade beräkningar
Abstract [en]

An effective strategy in dense linear algebra is the design of algorithms as tiled algorithms. Tiled algorithms that express the bulk of the computation as matrix-matrix operations (level-3 BLAS) have proven successful in achieving high performance on cache-based architectures. At the same time, tiled algorithms interoperate with dynamic data-driven execution models such as task parallelism and promise good parallel scalability.

This thesis applies the concept of tiled algorithms and task-centric execution to algorithms related to the computation of eigenvectors for the dense, non-symmetric eigenvalue problem. First, a standard algorithm for computing eigenvectors from the Schur form is recast such that all computational steps are rich in matrix-matrix operations. Second, inverse iteration on the Hessenberg matrix as an alternative approach to computing eigenvectors is addressed. An existing algorithm is revised to express the computationally most expensive step with matrix-matrix operations. Third, a task-parallel, tiled triangular Sylvester equation solver is amended to solve a larger class of problems. All algorithms have an enhanced performance, which is demonstrated through numerical experiments.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University, 2021. s. 27
Serie
Report / UMINF, ISSN 0348-0542 ; 21.05
Nyckelord
high-performance computing, standard non-symmetric eigenvalue problem, triangular Sylvester equation, tiled algorithms, task parallelism
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-185734 (URN)978-91-7855-577-2 (ISBN)978-91-7855-576-5 (ISBN)
Disputation
2021-09-20, MA316, MIT-huset, plan 3, Umeå, 10:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2021-08-30 Skapad: 2021-07-04 Senast uppdaterad: 2021-07-05Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Schwarz, Angelika BeatrixKjelgaard Mikkelsen, Carl ChristianKarlsson, Lars

Sök vidare i DiVA

Av författaren/redaktören
Schwarz, Angelika BeatrixKjelgaard Mikkelsen, Carl ChristianKarlsson, Lars
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Parallel Computing
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 206 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