Time and Parallel Processor Bounds for Linear Recurrence Systems
- 1 July 1975
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-24 (7) , 701-717
- https://doi.org/10.1109/t-c.1975.224291
Abstract
We give new time and processor bounds for the parallel evaluation of linear recurrence systems. Such systems may be represented as x̄ =c̄ + Ax̄ where A is an n X n strictly lower triangular matrix and c is a constant column vector. We show that O og22n) time steps and n3/ 8 + 0O2) processors are sufficient. We also show that mth order linear recurrences, i. e., where A has a bandwidth of m, can be computed within O(log2mlog2n) time steps with at most 3m2n/4 + O(mn) processors. In all cases, our bounds on time and processors are improvements on previous results, and the computer need only perform one type of operation at each time step (SIMD operation). By a simple transformation, the results can also be applied to the solution of any triangular linear system of equations Ax̄ = b̄.Keywords
This publication has 4 references indexed in Scilit:
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973
- On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting SpeedupIEEE Transactions on Computers, 1972
- The Organization and Use of Parallel MemoriesIEEE Transactions on Computers, 1971
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967