SOLVING TRIANGULAR SYSTEMS ON A PARALLEL COMPUTER

AHMED H. SAMEH AND RICHARD P. BRENT

Abstract

We present alternative formulations of the algorithms of Chen and Kuck [1] for the parallel solution of triangular systems of linear equations in O(log^{2} n) 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, showing that if x̃ is the computed solution of the triangular system Lx = f, then it satisfies the equation (L + δL)x̃ = f, where ∥δL∥ ≤ O(n^{2} log n)εκ^{2}(L)∥L∥. Here κ(L) is the condition number of L, ∥ · ∥ denotes the ∞-norm, and ε is the unit roundoff.

Comments

Only the Abstract is given here. The full paper appeared as [2].

References

1. S. C. Chen and D. J. Kuck, “Time and parallel processor bounds for linear recurrence systems”, IEEE Transactions on Computers C–24 (1975), 701–717.

2. 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, Zbl 375.65016. Also appeared as Report TR UIUCDCS-R-75-766, Department of Computer Science, University of Illinois, Urbana, Illinois (November 1975), 18 pp. rpb041.

(Sameh) Department of Computer Science and Centre for Advanced Computation, University of Illinois, Urbana, Illinois 61801

(Brent) Computer Centre, Australian National University, Canberra

1991 Mathematics Subject Classification. Primary 65G05; Secondary 65F05, 65Y05, 65Y10. Key words and phrases. Linear equations, triangular system, parallel algorithm, linear recurrence,

Chen and Kuck algorithm, error analysis.

Received by the editors November 14, 1975, and in final revised form November 9, 1976. This work was supported by the National Science Foundation under Grants USNSF DCR73-07980

A02 and MCS-7521758.

We thank John Larson for performing the numerical experiments. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1977, SIAM. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb041a typeset using AMS-L^{A}TEX