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
Scalable 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-4675-7434
2019 (Engelska)Ingår i: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 85, s. 131-140Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We present two task-centric algorithms for computing selected eigenvectors of a non-symmetric matrix reduced to real Schur form. Our approach eliminates the sequential phases present in the current LAPACK/ScaLAPACK implementation. We demonstrate the scalability of our implementation on multicore, manycore and distributed memory systems.

Ort, förlag, år, upplaga, sidor
Elsevier, 2019. Vol. 85, s. 131-140
Nyckelord [en]
Eigenvectors, Real Schur form, Tiled algorithmsMPI + OpenMP parallel programming
Nationell ämneskategori
Datorsystem
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-159296DOI: 10.1016/j.parco.2019.04.001ISI: 000471087700012Scopus ID: 2-s2.0-85064437701OAI: oai:DiVA.org:umu-159296DiVA, id: diva2:1317645
Forskningsfinansiär
EU, Horisont 2020, 671633eSSENCE - An eScience Collaboration, UFV 2010/149Tillgänglig från: 2019-05-23 Skapad: 2019-05-23 Senast uppdaterad: 2023-03-23Bibliografiskt granskad
Ingår i avhandling
1. Towards efficient overflow-free solvers for systems of triangular type
Öppna denna publikation i ny flik eller fönster >>Towards efficient overflow-free solvers for systems of triangular type
2019 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Triangular linear systems are fundamental in numerical linear algebra. A triangular linear system has a straight-forward and efficient solution strategy, namely forward substitution for lower triangular systems and backward substitution for upper triangular systems. Triangular systems, or, more generally, systems of triangular type occur frequently in algorithms for more complex problems. This thesis addresses three systems that involve linear systems of triangular type. The first system concerns quasi-triangular matrices. Quasi-triangular matrices are block triangular with 1-by-1 and 2-by-2 blocks on the diagonal. Quasi-triangular systems arise in the computation of eigenvectors from the real Schur form for the non-symmetric eigenvalue problem. This thesis contributes two algorithms for the eigenvector computation, which solve shifted quasi-triangular linear systems in an efficient and scalable way. The second system addresses scaled triangular linear systems. During the solution of a triangular linear system, the entries of the solution can grow. This growth can exceed the representable range of floating-point numbers. Such an overflow can be avoided by solving a scaled triangular system. The solution is scaled prior to every operation that would otherwise result in an overflow. After scaling, the operations can be executed safely. This thesis analyzes the scalability of a recently developed tiled, robust solver for scaled triangular systems, which ensures that at no point in the computation the overflow threshold is exceeded. The third system tackles the scaled continuous-time triangular Sylvester equation, which couples two quasi-triangular matrices. The solution process is prone to overflow. This thesis contributes a robust, tiled solver and demonstrates its practicability. These three systems can be addressed with a variation of forward or backward substitution. Compared to the highly optimized and scalable implementations of standard forward and backward substitution available in HPC libraries,the existing implementations of these three systems run at a smaller fraction of the peak performance. This thesis presents techniques to improve on the performance and robustness of the implementations of the three systems.

Ort, förlag, år, upplaga, sidor
Umeå: Department of computing science, Umeå University, 2019. s. 18
Serie
Report / UMINF, ISSN 0348-0542 ; 19.05
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-159436 (URN)978-91-7855-084-5 (ISBN)
Handledare
Tillgänglig från: 2019-05-28 Skapad: 2019-05-28 Senast uppdaterad: 2023-03-07Bibliografiskt granskad
2. 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 BeatrixKarlsson, Lars

Sök vidare i DiVA

Av författaren/redaktören
Schwarz, Angelika BeatrixKarlsson, Lars
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Parallel Computing
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

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