Изменение суммы префикса

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]

За пределами способов решения этих двух вариантов, мне интересно, есть ли ресурсы, которые покрывают как приспособить проблемы как вышеупомянутые в форму суммы префикса. Или, в более общем смысле, методы принятия / адаптации суммы префикса для повышения ее гибкости.

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.