Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Blocked Algorithms for Robust Solution of Triangular Linear Systems
verfasst von : Carl Christian Kjelgaard Mikkelsen, Lars Karlsson
Erschienen in: Parallel Processing and Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We consider the problem of computing a scaling \(\alpha \) such that the solution \({\varvec{x}}\) of the scaled linear system \({\varvec{Tx}} = \alpha {\varvec{b}}\) can be computed without exceeding an overflow threshold \(\varOmega \). Here \({\varvec{T}}\) is a non-singular upper triangular matrix and \({\varvec{b}}\) is a single vector, and \(\varOmega \) 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.