A parallel first-order linear recurrence solver
Gérard G. L. Meyer, Louis J. Podrazik · Journal of Parallel and Distributed Computing · 1987
In this paper we present a parallel procedure for the solution of first-order linear recurrence systems of size N when the number of processors p is small in relation to N. We show that when 1 < p2 ⩽ N, a first-order linear recurrence system of size N can be solved in 5(N − 1)(p + 1) steps on a p processor SIMD machine and at most 5(N − 12)/(p + 32) steps on a p processor MIMD machine. As a special case, we further show that our approach precisely achieves the lower bound 2(N − 1)(p + 1) for solving the parallel prefix problem on a p processor machine.