Solving Triangular Systems on a Parallel Computer
Ahmed Sameh, Richard P. Brent · SIAM Journal on Numerical Analysis · 1977
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.
Cited by 88 works. doi:10.1137/0714076
Authors
References
- The Theory of Matrices in Numerical Analysis.
- THE THEORY OF MATRICES IN NUMERICAL ANALYSIS
- THE COMPUTATIONAL COMPLEXITY OF ALGEBRAIC AND NUMERIC PROBLEMS.
- The Parallel Evaluation of General Arithmetic Expressions
- Rounding Errors in Algebraic Processes
- Time and Parallel Processor Bounds for Linear Recurrence Systems
- On the efficient computation of recurrence relations
- Roundoff Analysis by Direct Comparison of Two Algorithms
- Parallel solution methods for triangular linear systems of equations