Solving Triangular Systems on a Parallel Computer

In this paper, alternative formulations of the algorithms of Chen and Kuck are presented and a detailed error analysis is given, showing that if $\tilde x$ is the computable number, then Chen-Kuck algorithms are invalid.

Abstract

In this paper we present alternative formulations of the algorithms of Chen and Kuck [IEEE Trans, Computers (1975)]. We also give a detailed error analysis, showing that if $\tilde x$ is the computed solution of the triangular system $Lx = f$, then it satisfies the equation $(L + \delta L)\tilde x = f$ where $\| {\delta L} \| \leqq O(n^2 \log n)\varepsilon \kappa ^2 (L)\| L \|$. Here $\kappa (L)$ is the condition number of L, $\| \cdot \|$ denotes the $\infty $-norm, and $\varepsilon $ is the unit roundoff.