Premium
Parallel robust solution of triangular linear systems
Author(s) -
Kjelgaard Mikkelsen Carl Christian,
Schwarz Angelika Beatrix,
Karlsson Lars
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5064
Subject(s) - solver , linear system , eigenvalues and eigenvectors , scaling , computation , computer science , floating point , algorithm , set (abstract data type) , triangular matrix , parallel computing , mathematics , mathematical analysis , geometry , invertible matrix , physics , quantum mechanics , pure mathematics , programming language
Summary 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 .