Вычисление FFT на GPU

Ну и не только к FFT - хотелось-бы простенький пример, так сказать Getting Started.

Подразумевается NVidia, если это важно.

google Cooley-Tuckey?

Да нет, считать нужно еще быстрее. Более того считать нужно ПФ от непрерывно поступающих данных с окном постоянной длинны. Причем желательно чтобы окно каждый раз смещалось только на 1. Реальное смещение будет зависеть от производительности того что получится.

Если смещение на 1 сэмпл, это означает, что из предыдущего спектра надо выкинуть линию, которая ушла из-за смещения, и прибавить новую?

тьфу, погнал конечно

Хотя... не совсем погнал. Если смещение будет каждый раз одинаковым, то каждый раз надо будет отнять одну частоту, добавить новую и умножить на постоянную, которая зависит от смещения. А преобразование для каждого окна делать не придётся.

Ну а теперь алгоритмик в двух словах как это сделать не пересчитывая все?

А для проверки можно например подать сначала много нулей, а потом много нулей-1 и единичку и посмотерть, что изменилась далеко не одна частота.

http://www.mathematik.uni-dortmund.de/~goeddeke/gpgpu/

Там кучка ссылок на туториалы по вычислениям на GPU.

По-моему, основной недостаток преобразования Фурье заключается в том, что он позволяет локализовать частотную составляющую сигнала с абсолютной точностью, а временную --- не локализует вообще. Присмотрись к вейвлетам, возможно они сильно облегчат твою жизнь.

Пусть есть две последовательности чисел {a0, a1, ..., aN} i {a1, a2, ..., aN+1}, которые отличаются только первым и последним элементами. если FT1={b0, ..., bN} - преобразование первой последовательности, то для второй будет: bk = FT1*eхp(-ik/(N+1)) - sum(a0*eхp(i(k-1)n/(N+1)) + sum(a(N+1)*eхp(ikn/(N+1))

> Подразумевается NVidia, если это важно.

это

http://developer.download.nvidia.com/compute/cuda/1_0/CUFFT_Library_1.0.pdf

разве не оно?