ищу параллельный алгоритм

[Горьковчанин]

приветствую группу!

Ищу параллельный алгоритм вычисления свёртки двух векторов $x=(x_1,\ldots,x_n)$, $y=(y_1, \ldots, y_n)$ по формуле $z_i=\sum\limits_{j=1}^{i} x_jy_{i-j+1}$. По факту такая штука встречается при нахождении распределения суммы независимых дискретных случайный величин. Можно эффективно вычислять такое на кластере?

[maxal]

Во-первых, удобнее сдвинуть индексы: $x=(x_0,\dots,x_{n-1})$ и $y=(y_0,\dots,y_{n-1}).$ Тогда

$$z_i = \sum_{j=0}^i x_i y_{i-j}.$$

Далее, рассмотрим многочлены $f(t) = \sum_{i=0}^{n-1} x_i t^i$ и $g(t) = \sum_{i=0}^{n-1} y_i t^i.$ Тогда $z_i$ есть ни что иное как коэффициент при $x^i$ в произведении $f(t)g(t).$

Таким образом, чтобы найти все $z_i$ скопом достаточно вычислить произведение многочленов $f(t)g(t).$ Ну а для этого есть быстрое преобразование Фурье...

[Горьковчанин]

maxal писал(а):

Таким образом, чтобы найти все $z_i$ скопом достаточно вычислить произведение многочленов $f(t)g(t).$ Ну а для этого есть быстрое преобразование Фурье...

Это очевидно. Где бы найти в электронном желательно виде описание ПАРАЛЛЕЛЬНОГО варианта БПФ?

[maxal]

Где найти - в гугле!

Вот например: http://beige.ucs.indiana.edu/B673/node15.html