Answers are grounded in this paper and cite their sources.
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̄.
No takes yet. Share an insight, caveat, or question.
Chen et al. (1975) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: