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
Blocked Algorithms for Robust Solution of Triangular Linear Systems
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-9158-1941
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4675-7434
2018 (English)In: Parallel Processing and Applied Mathematics: 12th International Conference, PPAM 2017, Lublin, Poland, September 10-13, 2017, Revised Selected Papers, Part I / [ed] Roman Wyrzykowski, Jack Dongarra, Ewa Deelman, Konrad Karczewski, Springer, 2018, Vol. 1, p. 68-78Conference paper, Published paper (Refereed)
Abstract [en]

We consider the problem of computing a scaling α such that the solution x of the scaled linear system Tx = αb can be computed without exceeding an overflow threshold Ω. Here T is a non-singular upper triangular matrix and b is a single vector, and Ω is less than the largest representable number. This problem is central to the computation of eigenvectors from Schur forms. We show how to protect individual arithmetic operations against overflow and we present a robust scalar algorithm for the complete problem. Our algorithm is very similar to xLATRS in LAPACK. We explain why it is impractical to parallelize these algorithms. We then derive a robust blocked algorithm which can be executed in parallel using a task-based run-time system such as StarPU. The parallel overhead is increased marginally compared with regular blocked backward substitution.

Place, publisher, year, edition, pages
Springer, 2018. Vol. 1, p. 68-78
Series
Theoretical Computer Science and General Issues, ISSN 0302-9743, E-ISSN 1611-3349 ; 10777
Keywords [en]
Triangular linear systems, overflow, blocked algorithms, robust algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-154296DOI: 10.1007/978-3-319-78024-5_7ISI: 000458563300007Scopus ID: 2-s2.0-85044716269ISBN: 978-3-319-78023-8 (print)ISBN: 978-3-319-78024-5 (electronic)OAI: oai:DiVA.org:umu-154296DiVA, id: diva2:1271006
Conference
12th International Conference, PPAM 2017, Lublin, Poland, September 10-13, 2017
Available from: 2018-12-14 Created: 2018-12-14 Last updated: 2019-04-16Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Kjelgaard Mikkelsen, Carl ChristianKarlsson, Lars

Search in DiVA

By author/editor
Kjelgaard Mikkelsen, Carl ChristianKarlsson, Lars
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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