Efficient Parallelization of a Ubiquitous Sequential Computation

We find a succinct expression for computing the sequence $x_t=a_t{x}_{t-1}+b_t$ in parallel with two prefix sums, given $t=(1,2,\dots ,n)$, $a_t\in {\mathbb{R}}^n$, $b_t\in {\mathbb{R}}^n$, and initial value $x_0\in \mathbb{R}$. On $n$ parallel processors, the computation of $n$ elements incurs $\mathcal{O}(\log n)$ time and $\mathcal{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 $\frac{n}{\log n}$.