Быстрое преобразование Фурье

Материал из Википедии — свободной энциклопедии

Быстрое преобразование Фурье — алгоритм, выполняющий дискретное преобразование Фурье за $O (N log(N))$ действий.

[править] Основной алгоритм

Покажем как выполнить дискретное преобразование Фурье за $O(N(p_1+\cdots+p_n))$ действий при $N=p_1p_2\cdots p_n$ . В частности, при $N = 2 n$ понадобится $O (N log(N))$ действий.

Дискретное преобразование Фурье преобразует набор чисел $a_0, \dots, a_{n-1}$ в набор чисел $b_0, \dots, b_{n-1}$ , такой, что $b_i=\sum_{j=0}^{n-1}a_j\varepsilon^{ij}$ , где $\varepsilon^n=1$ и $\varepsilon^k\neq 1$ при $1 < k < n$ . Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c $\varepsilon=e^{2\pi i/n}$ ) и к кольцам остатков.

Основной шаг алгоритма состоит в сведении задачи для $N$ чисел к задаче для $q = N / p$ числам, где $p$ — делитель $N$ . Пусть мы уже умеем решать задачу для $N / p$ чисел. Применим преобразование Фурье к наборам $a_i,a_{q+i}, \dots, a_{q(p-1)+i}$ для $i=0,1,\dots,q-1$ . Покажем теперь, как за $O (N p)$ действий решить исходную задачу. Заметим, что $b_i=\sum_{j=0}^{q-1} \varepsilon^{ij} (\sum_{k=0}^{p-1}a_{kq+j}\varepsilon^{kiq})$ . Выражения в скобках нам уже известны — это $i$ $\mod p$ -тое число после преобразования Фурье $j$ -той группы. Таким образом, для вычисления каждого $b i$ нужно $O (q)$ действий, а для вычисления всех $b i$ — $O (N q)$ действий, что и требовалось получить.

[править] Обратное преобразование Фурье

Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать $\varepsilon^{-1}$ вместо $\varepsilon$ и окончательный результат поделить на $N$ .

[править] Общий случай

Общий случай может быть сведён к предыдущему. Пусть $4N>2^k\ge2N$ . Заметим, что $b_i=\varepsilon^{-i^2/2}\sum_{j=0}^{N-1}\varepsilon^{(i+j)^2/2}\varepsilon^{-j^2/2}a_j$ . Обозначим $\bar{a}_i=\varepsilon^{-i^2/2}a_i, \bar{b}_i=\varepsilon^{i^2/2}b_i, c_i=\varepsilon^{(2N-2-i)^2/2}$ . Тогда $\bar{b}_i=\sum_{j=0}^{2N-2-i}\bar{a}_jc_{2N-2-i-j}$ , если положить $\bar{a}_i=0$ при $i\ge N$ .

Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для $2 k$ элементов. Выполняем прямое преобразование Фурье для $\{\bar{a}_i\}_{i=0}^{i=2^k-1}$ и $\{c_i\}_{i=0}^{i=2^k-1}$ , перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Вычисления всех $\bar{a}_i$ и $c i$ требуют $O (N)$ действий, три преобразования Фурье требуют $O (N log(N))$ действий, перемножение результатов преобразований Фурье требует $O (N)$ действий, вычисление всех $b i$ зная значения свертки требует $O (N)$ действий. Итого для дискретного преобразования Фурье требуется $O (N log(N))$ действий для любого $N$ .