Robust Solution of Triangular Linear Systems

We consider the problem of computing a scaling α such that the solution x of the scaled linear system Tx=\alpha b can be computed without exceeding the overflow threshold $\Omega$. Here T is a non-singular upper triangular matrix and b is a single vector. 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 and our main contribution is to simplify and extend the analysis. We explain why it is impractical to parallelize these algorithms. We then derive a robust block algorithm for solving triangular linear systems. Any run-time system such as StarPU which can run a task based backward substitution algorithm can also execute our robust block algorithm in parallel. It is simply a matter of replacing standard kernels with our robust kernels.NLAFE