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
Scalable eigenvector computation for the non-symmetric eigenvalue problem
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4675-7434
2019 (English)In: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 85, p. 131-140Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
Elsevier, 2019. Vol. 85, p. 131-140
Keywords [en]
Eigenvectors, Real Schur form, Tiled algorithmsMPI + OpenMP parallel programming
National Category
Computer Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-159296DOI: 10.1016/j.parco.2019.04.001ISI: 000471087700012OAI: oai:DiVA.org:umu-159296DiVA, id: diva2:1317645
Funder
EU, Horizon 2020, 671633eSSENCE - An eScience Collaboration, UFV 2010/149Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2019-07-10Bibliographically approved
In thesis
1. Towards efficient overflow-free solvers for systems of triangular type
Open this publication in new window or tab >>Towards efficient overflow-free solvers for systems of triangular type
2019 (English)Licentiate thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Umeå: Department of computing science, Umeå University, 2019. p. 18
Series
Report / UMINF, ISSN 0348-0542 ; 19.05
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-159436 (URN)978-91-7855-084-5 (ISBN)
Supervisors
Available from: 2019-05-28 Created: 2019-05-28 Last updated: 2019-05-28Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Schwarz, Angelika BeatrixKarlsson, Lars

Search in DiVA

By author/editor
Schwarz, Angelika BeatrixKarlsson, Lars
By organisation
Department of Computing Science
In the same journal
Parallel Computing
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 63 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