New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
- 1 April 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (2), 252-261
- https://doi.org/10.1145/321941.321945
Abstract
The parallel evaluation of rational expressions is considered. New algorithms which minimize the number of multiplication or division steps are given. They are faster than the usual algorithms when multiplication or division takes more time than addition or subtraction. It is shown, for example, that x n can be evaluated in two steps of parallel division and ⌈log 2 n ⌉ steps of parallel addition, while the usual algorithm takes ⌈log 2 n ⌉ steps of parallel multiplication. Lower bounds on the time required are obtained in terms of the degree of the expressions to be evaluated. From these bounds, the algorithms presented in the paper are shown to be asymptotically optimal. Moreover, it is shown that by using parallelism the evaluation of any first-order rational recurrence of degree greater than 1, e.g. y i +1 = 1/2;( y i + a / y i ), and any nonlinear polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used and how large the size of the problem is.Keywords
This publication has 9 references indexed in Scilit:
- A Determinant Theorem with Applications to Parallel AlgorithmsSIAM Journal on Numerical Analysis, 1974
- Parallel Solution of Recurrence ProblemsIBM Journal of Research and Development, 1974
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973
- Optimal algorithms for parallel polynomial evaluationJournal of Computer and System Sciences, 1973
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of EquationsJournal of the ACM, 1973
- On the Parallel Evaluation of PolynomialsIEEE Transactions on Computers, 1973
- On the Addition of Binary NumbersIEEE Transactions on Computers, 1970
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967
- Very high-speed computing systemsProceedings of the IEEE, 1966