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
Towards efficient overflow-free solvers for systems of triangular type
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
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: urn:nbn:se:umu:diva-159436ISBN: 978-91-7855-084-5 (tryckt)OAI: oai:DiVA.org:umu-159436DiVA, id: diva2:1318540
Handledare
Tillgänglig från: 2019-05-28 Skapad: 2019-05-28 Senast uppdaterad: 2019-05-28Bibliografiskt granskad
Delarbeten
1. Scalable eigenvector computation for the non-symmetric eigenvalue problem
Öppna denna publikation i ny flik eller fönster >>Scalable eigenvector computation for the non-symmetric eigenvalue problem
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
Nyckelord
Eigenvectors, Real Schur form, Tiled algorithmsMPI + OpenMP parallel programming
Nationell ämneskategori
Datorsystem
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-159296 (URN)10.1016/j.parco.2019.04.001 (DOI)000471087700012 ()
Forskningsfinansiär
EU, Horisont 2020, 671633eSSENCE - An eScience Collaboration, UFV 2010/149
Tillgänglig från: 2019-05-23 Skapad: 2019-05-23 Senast uppdaterad: 2019-07-10Bibliografiskt granskad
2. Parallel robust solution of triangular linear systems
Öppna denna publikation i ny flik eller fönster >>Parallel robust solution of triangular linear systems
2019 (Engelska)Ingår i: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 31, nr 19, artikel-id e5064Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Triangular linear systems are central to the solution of general linear systems and the computation of eigenvectors. In the absence of floating‐point exceptions, substitution runs to completion and solves a system which is a small perturbation of the original system. If the matrix is well‐conditioned, then the normwise relative error is small. However, there are well‐conditioned systems for which substitution fails due to overflow. The robust solvers xLATRS from LAPACK extend the set of linear systems which can be solved by dynamically scaling the solution and the right‐hand side to avoid overflow. These solvers are sequential and apply to systems with a single right‐hand side. This paper presents algorithms which are blocked and parallel. A new task‐based parallel robust solver (Kiya) is presented and compared against both DLATRS and the non‐robust solvers DTRSV and DTRSM. When there are many right‐hand sides, Kiya performs significantly better than the robust solver DLATRS and is not significantly slower than the non‐robust solver DTRSM.

Ort, förlag, år, upplaga, sidor
John Wiley & Sons, 2019
Nyckelord
Overflow protection, parallel algorithms, task-based parallelism, triangular linear systems
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-154297 (URN)10.1002/cpe.5064 (DOI)000486203400007 ()2-s2.0-85056329436 (Scopus ID)
Anmärkning

Special Issue

Tillgänglig från: 2018-12-14 Skapad: 2018-12-14 Senast uppdaterad: 2019-11-11Bibliografiskt granskad
3. Robust Task-Parallel Solution of the Triangular Sylvester Equation
Öppna denna publikation i ny flik eller fönster >>Robust Task-Parallel Solution of the Triangular Sylvester Equation
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Abstract [en]

The Bartels-Stewart algorithm is a standard approach to solving the dense Sylvester equation. It reduces the problem to the solution of the triangular Sylvester equation. The triangular Sylvester equation is solved with a variant of backward substitution. Backward substitution is prone to overflow. Overflow can be avoided by dynamic scaling of the solution matrix. An algorithm which prevents overflow is said to berobust. The standard library LAPACK contains the robust scalar sequential solver dtrsyl. This paper derives a robust, level-3 BLAS-based task-parallel solver. By adding overflow protection, our robust solver closes the gap between problems solvable by LAPACK and problems solvable by existing non-robust task-parallel solvers. We demonstrate that our robust solver achieves a similar performance as non-robust solvers.

Nyckelord
Overflow protection, task parallelism, triangular Sylvester equation, real Schur form
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-159435 (URN)
Forskningsfinansiär
EU, Horisont 2020, 671633
Tillgänglig från: 2019-05-28 Skapad: 2019-05-28 Senast uppdaterad: 2020-02-27Bibliografiskt granskad

Open Access i DiVA

kappa(394 kB)55 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 394 kBChecksumma SHA-512
a98d0e731111946aa79706ae38b070772741ca7872b99ce6bd7a6f47d9079905c768afd59d7b0a03c638d60fb3766d84c2de70754d8810c0dc122c7a18644fc3
Typ fulltextMimetyp application/pdf

Personposter BETA

Schwarz, Angelika Beatrix

Sök vidare i DiVA

Av författaren/redaktören
Schwarz, Angelika Beatrix
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 55 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 258 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