Участник:Ivanov.kir.m/Быстрое дискретное преобразование Фурье

Алгоритм Кули-Тьюки одномерного преобразования Фурье для действительных чисел
Последовательный алгоритм
Последовательная сложность	[math]O (N \log N)[/math]
Объём входных данных	[math]N[/math] действительных чисел
Объём выходных данных	[math]\lfloor N/2 \rfloor+1[/math] комплексных чисел
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O (\log N)[/math]
Ширина ярусно-параллельной формы	[math]N[/math]

Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого  вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем [math]O(N^{2})[/math], требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность [math]O(N\log(N))[/math]. Cуществует несколько различных алгоритмов для вычисления ДПФ считающимся быстрым преобразование Фурье:

• Алгоритм Кули-Тьюки [1]
• Алгоритм Гуда-Томаса [2]
• Алгоритм Бруна [3]
• Алгоритм Блюштейна [4]

1 ЧАСТЬ. Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Одним из вариантов быстрого преобразования Фурье для вектора действительных чисел с размерностью равной степени двойки является алгоритм Кули-Тьюки. Отличительной особенностью данного алгоритма является то, что он обходится без использования специфических приемов, использующихся именно для степеней четверки, восьмерки и т.п. Однако благодаря тому, что на вход данному алгоритму подается вектор чисто вещественных чисел, выходной вектор удовлетворяет эрмитовой избыточности (Hermitian redundancy) , т.е. [math]out[i][/math] является сопряженным с [math]out[n-i][/math]. Это обстоятельство позволяет достичь роста скорости и снижения затрат памяти примерно в 2 раза по сравнению с комплексным аналогом алгоритма.

1.2 Математическое описание алгоритма

Входные данные: вектор действительных чисел [math]a = (a_1,a_2,...,a_N)[/math].

Выходные данные: вектор комплексных чисел [math]b = (b_1,b_2,...,b_{\lfloor N/2 \rfloor+1})[/math].

Замечание: В простейшем случае алгоритм Кули-Тьюки применяется к векторам размерности степени двойки, поэтому на практике вектора иной размерности часто дополнять до ближайшей степени двойки. Такой подход делает алгоритм Кули-Тьюки не самым эффективным алгоритмом БПФ, поскольку дополнение до степени двойки может сильно усложнить задачу.

1.3 Рекурсивное описание

Алгоритм:

1. Входной вектор [math]a = (a_0,a_2,...,a_{N-1})[/math] преобразуется в матрицу [math]A[/math] размера [math]n_1 \times n_2 [/math], где [math]N=n_1 \cdot n_2[/math] и [math]n_1 \lt n_2[/math]

[math] A = \begin{pmatrix} a_0 & a_1 & \cdots & a_{n_1-1} \\ a_{n_1} & a_{n_1+1} & \cdots & a_{2n_1-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{(n_2-1)\cdot n_1} & a_{(n_2-1)\cdot n_1+1} & \cdots & a_{n_2\cdot n_1-1} \end{pmatrix} [/math]

1. К каждой строке полученной матрицы применяется быстрое дискретное преобразование Фурье (БПФ) порядка [math]n_1[/math]
2. Каждый элемент полученный после применения БПФ умножается на поворотные множители [math]exp (2 \pi i(m-1)(j-1)/N)[/math], где [math]m[/math] - номер строки, а [math]j[/math] - номер столбца
3. Полученная после шагов 1-2 матрица [math]A[/math] транспонируется
4. К каждой строке матрицы [math]A^T[/math] применяется БПФ порядка [math]n_2[/math]

Замечание: Как правило все поворотные множители вычисляются заранее и хранятся в специальном массиве.

1.4 Вычислительное ядро алгоритма

В случае размерности входа равной степени двойки, вычислительным ядром алгоритма является, так называемая, "бабочка". В простейшем случае "бабочка" представляет из себя двухточечное преобразование. Рассмотрим этот случай:

На вход алгоритму подается двухэлементный вектор ‒ [math] v = (v[0], v[1]) [/math]. Тогда для вычисления будут происходить по следующим формулам:

[math]V[0] = W_2^0 v[0] + W_2^0 v[1] = v[0] + W_2^0 v[1] [/math]

[math]V[1] = W_2^0 v[0] + W_2^1 v[1] = v[0] + W_2^1 v[1] [/math]

Данный процесс удобно изобразить с помощью следующей схемы:

Для 4-х элеметного вектора [math]v=(v[0],v[1],v[2],v[3])[/math], алгоритм строится похожим образом. Сначала создаются простейшие "бабочки", а потом их результаты соединяются с противоположеной "бабочкой":

[math]V[0]=v[0]+W_2^0 v[2]+W_4^0(v[1]+W_2^0 v[3])[/math]

[math]V[1]=v[0]-W_2^0 v[2]+W_4^1(v[1]-W_2^0 v[3])[/math]

[math]V[2]=v[0]+W_2^0 v[2]-W_4^0(v[1]+W_2^0 v[3])[/math]

[math]V[3]=v[0]-W_2^0 v[2]-W_4^1(v[1]-W_2^0 v[3])[/math]

Схема в таком случае будет выглядеть следующим образом:

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

1.5 Макроструктура алгоритма

Для исходного вектора [math]a = (a_1,a_2,...,a_N)[/math] размерности [math]N = n_1 \cdot n_2[/math], [math]n_1 \lt n_2[/math] БПФ представляется как:

1. [math]n_2[/math] БПФ порядка [math]n_1[/math]
2. [math]n_1 \cdot n_2[/math] умножение комплексных чисел
3. [math]n_1[/math] БПФ порядка [math]n_2[/math]

1.6 Схема реализации последовательного алгоритма

Схема организации состоит в том, что на каждом шаге [math]i[/math] для выполнения "бабочки" все элементы разбиваются на [math]n_{i_1}[/math] векторов по [math]n_{i_2}[/math] элементов, причем [math]n_{i_1} \cdot n_{i_2} = n_i[/math], где [math]n_i[/math] длина входного вектора на текущем шаге [math]i[/math]. В случае если такое разбиение невозможно, по причине того что [math]n_i[/math] простое число, исходный вектор на текущем шаге дополняется элементом. В зависимости от номера шага, разница координат для каждой пары элементов увеличивается соразмерно разбиению [math](n_{i_1},n_{i_2})[/math]. При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

1.7 Последовательная сложность алгоритма

Быстрое дискретное преобразование Фурье выполнимо за [math]O(N(n_1+\cdots+n_m))[/math] действий при [math]N=n_1n_2\cdots n_m[/math] (в простом случае, при [math]N=2^m[/math] необходимо [math]O(N\log_2(N))[/math] действий).Дискретное преобразование Фурье преобразует вектор [math]a = (a_0, \dots, a_{N-1})[/math] в вектор комплексных чисел [math]b = (b_0, \dots, b_{N-1})[/math], такой, что [math]b_i=\sum_{j=0}^{N-1}a_j\varepsilon^{ij}[/math], где [math]\varepsilon^n=1[/math] и [math]\varepsilon^k\neq 1[/math] при [math]0\lt k\lt N[/math].

Основной шаг алгоритма состоит в сведении задачи для [math]N[/math] чисел к задаче для [math]n_1=N/n_2[/math] числам, где [math]n_2[/math] — делитель [math]N[/math]. Пусть мы уже умеем решать задачу для [math]N/n_2[/math] чисел. Применим преобразование Фурье к векторам [math]a_i,a_{n_2+i}, \dots, a_{n_2(n_1-1)+i}[/math] для [math]i=0,1,\dots,n_2-1[/math]. Покажем теперь, что за [math]O(Np)[/math] действий можно решить исходную задачу. Заметим, что [math]b_i=\sum_{j=0}^{n_2-1} \varepsilon^{ij} (\sum_{k=0}^{n_1-1}a_{kn_2+j}\varepsilon^{kin_2})[/math]. Выражения в скобках нам уже известны — это [math](i\pmod p)[/math]-тое число после преобразования Фурье [math]j[/math]-го вектора. Таким образом, для вычисления каждого [math]b_i[/math] нужно [math]O(n_2)[/math] действий, а для вычисления всех [math]b_i[/math] всего [math]O(Nn_2)[/math] действий, что и требовалось.

В общем случае :

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

Таким образом задача сведена к вычислению свёртки, а это можно сделать с помощью трёх преобразований Фурье для [math]2^k[/math] элементов. Выполняем прямое преобразование Фурье для [math](\bar{a_0}, \cdots, \bar{a}_{2^k-1})[/math] и [math](c_1,\cdots,c_{2^k-1})[/math], перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

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

1.8 Информационный граф

Информационный граф для БПФ где n1=6, n2=6. В левой части выполняется построчное преобразование входного массива, а в правой поколоночное методом перемножения матриц.

1.9 Ресурс параллелизма алгоритма

Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из [math]log(N)[/math] операций комплексного сложения/вычитания и [math]log(N)[/math] операций комплексного умножения (основание [math]log[/math] целиком зависит от выбранного на каждом шаге алгоритма разбиения). Таким образом, простой алгоритм БПФ в общем случае может быть отнесён к логарифмическому классу по параллельной сложности.

1.10 Входные и выходные данные алгоритма

Входные данные: вектор действительных чисел [math]a = (a_1,a_2,...,a_N)[/math].

Выходные данные: вектор комплексных чисел [math]b = (b_1,b_2,...,b_{\lfloor N/2 \rfloor+1})[/math].

1.11 Свойства алгоритма

Таким образом в общем у алгоритма БПФ в случае неограниченных ресурсов:

• последовательная сложность - линейно-логарифмическая
• параллельная сложность - логарифмическая.

При этом алгоритм полностью детерминирован.

2 ЧАСТЬ. Программная реализация алгоритма

В качестве тестируемой реализации была выбрана библиотека FFTW, а именно функция, выполняющая БПФ одномерного вектора действительных чисел.

2.2 Существующие реализации алгоритма

Наиболее известной библиотекой для выполнения различных вариантов быстрого преобразования Фурье является FFTW, разработанная Матео Фриго и Стивеном Джонсоном в Массачусетском технологическом институте. Для преобразования небольших объемов данных используется алгоритм Кули - Тьюки, в случае входа больших размеров используется алгоритм Радера или Блюштейна. Библиотека считается самой быстрой реализацией БПФ и на входах любых размеров и размерностей сохраняет ассимптотическую сложность [math]O(N\cdot log(N))[/math]. Также, существует версия FFTW с поддержкой MPI, которая позволяет с объемами данных не умещающимися в память.

FFTW изначально написана на языке C, однако имеет API для нескольких языков, в том числе Fortran и Ada. Открытая версия библиотеки распространяется под лицензией GNU General Public License. Также существует реализация для коммерческого использования распространяемая под лицензией MIT.

Существует несколько реализаций алгоритма, для рассчета на GPU:

• cuFFT для рассчета на графических ускорителях от NVIDIA.
• clFFT для рассчета на GPU и CPU.

3 Литература

[1] Википедия [Электронный ресурс]. Тема: Быстрое преобразование Фурье – Электрон. дан. – URL Быстрое преобразование Фурье (дата обращения 17.09.2016)