Solving triangular systems on a parallel computer

41. A. H. Sameh and R. P. Brent, Solving triangular systems on a parallel computer, SIAM J. Numerical Analysis 14 (1977), 1101-1113. MR 56#17026.

Abstract: dvi (3K), pdf (78K), ps (28K).

Paper: pdf (831K).


We present alternative formulations of the algorithms of Chen and Kuck [IEEE Transactions on Computers C-24 (1975), 701-717] for the parallel solution of triangular systems of linear equations in O((log n)2) steps. We consider both the dense and banded cases, and establish bounds on the time and number of processors required. We also give a detailed error analysis, obtaining a backward error bound proportional to the square of the condition number of the system (for details see the dvi, ps or pdf version of the abstract).

Go to next publication

Return to Richard Brent's index page