Эффективное вычисление свертки

stream_24

Колееги!
Возникла производственная необходимость наиболее эффективным образом вычислять свертку двух комплексных последовательностей. Буду премного благодарен как известным реализациям, так и материалам, в которых могут быть изложены мнения научного сообщества на сей счёт.
Заранее спасибо:)

soldatiki

берем быстрое преобразование Фурье (БПФ делаем умножение, берем обратное БПФ. Порядка N logN операций.

vovatroff

А что, бывает преобразование Фурье для дискретных последовательностей?
Это же не интегральные свертки имелись в виду...

stream_24

кстати, да...

vovatroff

Может, они и есть, я просто не в курсе.
В математике обычно все, что приходит в голову,
уже есть, стоит только поискать...

stream_24

Очень интересный подход!;-)
да, есть:) надо бы теперь реализовать всё как следует...

vovatroff

Нашлось что-то полезное?

vokus

Да, есть. Преобразование Фурье можно ввести очень много где, но в случае последовательностей чисел фиксированной длины n его можно ввести, если угодно, как обычный оператор Фурье на L_2(Z/nZ интегралом Фурье по считающей мере (если отождествить Z/nZ с комплексными корнями из единицы) . :-)
Подробнее см. http://en.wikipedia.org/wiki/Discrete_Fourier_transform

soldatiki

кстати, да...
кстати, да. Есть-то он, конечно, есть, но вот уже не помню, переводит ли он свертку в умножение. Да и при том, кажется, для последовательностей (обычных, не двусторонних) есть два типа свертки: обычная и кольцевая. В первом случае члены последовательности с отрицательными номерами и с номерами, большими некоторого максимального, полагаются нулями. Таким образом, последовательность считается финитной (это и есть наш массив данных). Во втором случае отождествляются элементы a[-k] и a[N-k], то есть, последовательность считается периодической, а суммирование идет по отрезку длиной в период (наш массив задает этот отрезок). С каким из этих двух преобразований связано почленное умножение Фурье-образов - не помню.

vokus

С кольцевой.
Оставить комментарий
Имя или ник:
Комментарий: