Time and Parallel Processor Bounds for Linear Recurrence Systems
Shyh-Ching Chen, David J. Kuck · IEEE Transactions on Computers · 1975
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̄.