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

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

Основной алгоритм

Покажем как выполнить дискретное преобразование Фурье за O(N(p_1+\cdots+p_n)) действий при N=p_1p_2\cdots p_n. В частности, при N = 2n понадобится O(Nlog(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(Np) действий решить исходную задачу. Заметим, что b_i=\sum_{j=0}^{q-1} \varepsilon^{ij} (\sum_{k=0}^{p-1}a_{kq+j}\varepsilon^{kiq}). Выражения в скобках нам уже известны — это i\mod p-тое число после преобразования Фурье j-той группы. Таким образом, для вычисления каждого bi нужно O(q) действий, а для вычисления всех biO(Nq) действий, что и требовалось получить.

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

Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать \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.

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

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

Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней 2N и 2k.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home