2023/10/27 by Franz A. Heinsen, Heinsen, Franz A. · 1 voice · 1 citation
#cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.2311.06281
We find a succinct expression for computing the sequence xt = at xt-1 + bt in parallel with two prefix sums, given t = (1, 2, …, 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 (n)/(log n).