I'm trying parallelize some software that performs some recursive linear equations. I think some of them might be adapted into prefix sums. A couple of examples of the kinds of equation I'm dealing with are below.
The standard prefix sum is defined as:
y[i] = y[i-1] + x[i]
One equation I'm interested in looks like prefix sum, but with a multiplication:
y[i] = A*y[i-1] + x[i]
Another is having deeper recursion:
y[i] = y[i-1] + y[i-2] + x[i]
Outside of ways of tackling these two variations, I'm wondering if there are resources that cover how to adapt problems like the above into prefix sum form. Or more generally, techniques for adopting/adapting prefix sum to make it more flexible.
(1)
y[i] = A*y[i-1] + x[i]
can be written as
y[z] = A^z * y[0] + Sum(A^(z-j) * x[j])
,where j E [z,1].
A^z * y[0] can be calculated in O(log(z))
Sum(A^(z-j) * x[j]) can be calculated in O(z).
If the maximum size of the sequence is known beforehand (say max), then you can precompute a modified prefix sum array of x as
prefix_x[i] = A*prefix_x[i-1] + x[i]
then Sum(A^(z-j) * x[j]) is simply prefix_x[z]
and the query becomes O(1) with O(max) precomputation.
(2)
y[i] = y[i-1] + y[i-2] + x[i]
can be written as
y[z] = (F[z] * y[1] + F[z-1] * y[0]) + Sum(F[z-j+1] * x[j])
,where j E [z,2] and F[x] = xth fibonaci number
(F[z] * y[1] + F[z-1] * y[0]) can be calculated in O(log(z))
Sum(F[z-j+1] * x[j]) can be calculated in O(z).
If the maximum size of the sequence is known beforehand (say max), then you can precompute a modified prefix sum array of x as
prefix_x[i] = prefix_x[i-1] + prefix_x[i-2] + x[i]
then Sum(F[z-j+1] * x[j]) is simply prefix_x[z]
and the query becomes O(1) with O(max) precomputation.