first order linear recurrence

p₁ = b₁
p_i = a_ip_i-1 + b_i

The problem is, given b₁ ... b_n and a₁ ... a_n, find all the values of p. Sequentially, the straightforward algorithm is to compute p₂ by replacing p₁ in the equation, and so on, the algorithm will take O(n) time.

In parallel, it at first seems that there is not much room for parallelization, since p_i needs the value of p_i-1. However, there are actually several ways to do this in O(log n) steps using O(n) processors. One possible algorithm is to use a prefix summing algorithm, another is to use a technique called odd-even reduction.