Efficient Parallelization of a Ubiquitous Sequential Computation

We find a succinct expression for computing the sequence xt = at xt-1 + bt in parallel with two prefix sums, given t = (1, 2, dots, n), at ∈ ℝn, bt ∈ ℝn, and initial value x0 ∈ ℝ. On n parallel processors, the computation of n elements incurs O(log n) time and O(n) space. Sequences of this form are ubiquitous in science and engineering, making efficient parallelization useful for a vast number of applications. We implement our expression in software, test it on parallel hardware, and verify that it executes faster than sequential computation by a factor of fracnlog n.