前缀和变化

Question

我正在尝试并行化某些执行递归线性方程的软件。我认为其中一些可能会被改编成前缀和。下面是我正在处理的方程式的几个例子。

标准前缀和定义为：

y[i] = y[i-1] + x[i]

我感兴趣的一个方程看起来像前缀和，但有一个乘法：

y[i] = A*y[i-1] + x[i]

另一个有更深层次的递归：

y[i] = y[i-1] + y[i-2] + x[i]

除了解决这两个变体的方法之外，我想知道是否有资源涵盖如何将上述问题调整为前缀和形式。或者更一般地说，adopting/adapting 前缀和的技术使其更加灵活。

Answer 1

(1)

y[i] = A*y[i-1] + x[i]

可以写成

y[z] = A^z * y[0] + Sum(A^(z-j) * x[j]) 
    ,where j E [z,1].

A^z * y[0]可以计算在O(log(z))

Sum(A^(z-j) * x[j])可以计算在O(z).

如果事先知道序列的最大大小（例如max），那么您可以预先计算x的修改后的前缀和数组为

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]

可以写成

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])可以计算在O(log(z))

Sum(F[z-j+1] * x[j])可以计算在O(z).

如果序列的最大大小事先已知（比如max），那么你可以预先计算一个修改后的x的前缀和数组为

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.

前缀和变化

Prefix sum variation

algorithm

computer-science-theory