A first order linear recurrence is defined as:

p1 = b1
pi = aipi-1 + bi

The problem is, given b1 ... bn and a1 ... an, find all the values of p. Sequentially, the straightforward algorithm is to compute p2 by replacing p1 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 pi needs the value of pi-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.

Log in or register to write something here or to contact authors.