Алговики - Вклад [ru]

Обсуждение участника:Chachba.A

2016-11-20T22:37:34Z

Weasel: /* Замечания к статье "Быстрое дискретное преобразование Фурье" */

== Замечания к статье ==

* п.п. 1.8, 1.9 не раскрыты--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 14:57, 25 октября 2016 (MSK)
** исправлено
* не указан конкретный вклад каждого автора--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 14:57, 25 октября 2016 (MSK)
** исправлено
* в п.п. 2.4 следует добавить описание компьютерной платформы, текст исследуемой программы.--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 13:41, 16 ноября 2016 (MSK)
** сделано

== Замечания к статье "Быстрое дискретное преобразование Фурье" ==

* Перенесите пожалуйста статью в личное пространство [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** а как это сделать? У нас нет прав на это, похоже
*** пункт 1 на этой странице, надо написать модератору: [[Алговики:Студенческие работы]]
**** написал запрос на перенос в личное пространство
* Раздел 1.1 - в самом первом абзаце стоит вставить обозначения двух фунций - f и f с крышкой, чтобы было ясно, что куда отображается. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* В общее описание алгоритма нужно вставить слова именно об алгоритме, а не только о математической задаче. В чем быстрота, за счет чего она достигается и т.д. Тут, в отличие от математического описания, не стоит увлекаться формулами. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Раздел 1.2 - существует обозначение части формулы через эпсилон, однако в следующей формуле он не встречается, странно. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Нужно пояснение, что происходит, когда N не представимо в виде произведения: применим ли алгоритм и в каких изменениях он нуждается. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
*** Обратите внимание на то, что объяснение других участников другое: [[Участник:Ivanov.kir.m/Быстрое дискретное преобразование Фурье]]
**** Сделано
* Нет данных о глубине рекурсии, написать об этом явно, скорее всего, в разделе "вычислительное ядро алгоритма". [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done

* Все хорошо, кроме переноса статьи (написал об этом) и дописывания разделов про программную реализацию алгоритма [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 12:43, 18 ноября 2016 (MSK)
** Дополнено

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-20T22:36:06Z

Weasel: /* Вычислительное ядро алгоритма */

{{Assignment|IgorS}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье, или спектром исходной функции, по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала, содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы «разделяй и властвуй». Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math> — число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> — простое число), то данный алгоритм напрямую не применим. На замену ему приходит алгоритм Радера, который в некотором смысле сводит задачу размерности <math>N</math> к подзадаче задаче размерности <math>N\pm 1</math> вычисления свертки, в которой допустимо и увеличение размерности до составных в том числе.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
Все запуски программы[http://pastebin.com/raw/xajKb9JN] проводились на с/к Blue Gene/P с использованием библиотеки Intel MKL.

IBM Blue Gene/P — массивно-параллельная вычислительная система, которая состоит из двух стоек, включающих 2048 четырехъядерных вычислительных узлов, с пиковой производительностью 27,9 терафлопс.

Характеристики системы:
* две стойки с вычислительными узлами и узлами ввода-вывода
* 1024 четырехъядерных вычислительных узла в каждой из стоек
* 16 узлов ввода-вывода в стойке (в текущей конфигурации активны 8, т.е. одна I/O-карта на 128 вычислительных узлов)
* программирование с использованием MPI, OpenMP/pthreads, POSIX I/O
* высокая энергоэффективность: ∼ 372 MFlops/W

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

Вычислительной узел:
* четыре микропроцессорных ядра PowerPC 450 (4-way SMP)
* пиковая производительность: 4 ядра x 3,4 GFlop/sec на ядро = 13,6 GFlop/sec
* пропускная способность памяти: 13,6 GB/sec
* 2 ГБ общей памяти
* 2 x 4 МБ кэш-памяти 2-го уровня (в документации по BG/P носит название L3)
* легковесное ядро (compute node kernel, CNK), представляющее собой Linux-подобную операционную систему, поддерживающую значительное подмножество Linux-совместимых системных вызовов
* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)
* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций

[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Обсуждение участника:Lineprinter

2016-11-20T22:10:50Z

Weasel:

== Перенос ==
Статья: [[Участник:Бобцов Борис/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]]
Выполняет: [[Участник:Бобцов Борис| Бобцов Борис]]

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]]
Выполняют: [[Участник:Greno4ka| Устинов Григорий ]] и [[ Лиджиев Данир ]]

Статья: [[Кластеризация сетями Кохонена]]
Выполняют: [[Участник:Kravtsovkirill| Кравцов Кирилл]] и [[Участник:Emaksimov| Максимов Егор]]

Статья: [[Нахождение собственных чисел квадратной матрицы методом QR разложения (2)]]
Выполняют: Баев Олег и Шевелев Александр

Статья: [[Стабилизированный метод биспоряженных градиентов (BiCGSTAB)]]
Выполняют: Гаврилов Алексей и Новиков Александр

Статья: [[Участники: Бобошко А., Юмакаева А./Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка]];
Выполняют: Бобошко Алексей и Юмакаева Алина

Статья: [[Алгоритм кластеризации, основанный на сетях Кохоннена]];
Выполняют: Логвиненко Александра и Адиев Тохтар

Статья: [[Ортогонализация Грама-Шмидта]];
Выполняют: [[Участник:KibAndrey| Кибанов Андрей]] и Аджиева Татьяна

Статья: [[Самоорганизующиеся карты Кохонена]];
Выполняет: [[Участник:Anton goy| Гой Антон]]

Статья:[[ЕМ-алгоритм_(Тематическое_моделирование)]];
Выполняют: Мурат Апишев и Андрей Заночкин

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья: [[Алгоритм_k-средних]]
Выполняют: [[Участник:Error2407|Богомазов Евгений]], [[Участник:Илья_Егоров|Егоров Илья]]

Статья: [[Алгоритм k-means]]
Выполняют: [[Участник:Бротиковская Данута|Данута Бротиковская]] и [[Участник:DennZo1993|Денис Зобнин]]

Статья: [[Partitioning Around Medoids (Алгоритм)]]
Выполняют: [[Участник:Denemmy| Галеев Данил]] и [[Участник:Ivan.Z| Запутляев Иван]]

Статья: [[Нечеткий_алгоритм_С_средних]]
Выполняют: [[Участник:Demon smd|Д.А.Гуськов]], [[Участник:marina abramenkova|М.А.Абраменкова]]

Статья: [[Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка]];
Выполняют: [[Участник:Алимов_Дамир_Алиевич|Алимов Дамир]] и [[Участник:Anlesnichiy|Антон Лесничий]]

Статья: [[Строгий_алгоритм_С_средних_(Hard_C-Means,_HCM)]];
Выполняют: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]] и [[Участник:Юрий_Комаров|Комаров Юрий]]

Статья: [[Алгоритм кластеризации, основанный на минимальном остовном дереве]];
Выполняет: [[Участник:Astandrik | Стандрик Антон Сергеевич]]

Статья: [[Умножение разреженной матрицы на вектор]];
Выполняет: [[Участник:Lexaloris | Новоселов Алексей]], Выполняет: [[Участник:kochet|П.А. Кочетков]]

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Участница:JuliaA|Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Статья:[[EM-алгоритм_кластеризации]]
Выполняет: [[Участник:Noite|Зинченко Дмитрий]]

Статья:[[Алгоритм_k_means]]
Выполняют: [[Участник:IanaV| Валуйская Яна]], [[Участник:GlotovES| Глотов Евгений]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы ЗП |Метод Якоби вычисления собственных значений симметричной матрицы ЗП]];
Выполняют: [[Участник:Зиновьев Владимир|Зиновьев В.С.]], [[Участник:Пронин Андрей|Пронин А.М.]]

Статья:[[Алгоритм_кластеризации,_основанный_на_минимальном_покрывающем_дереве]]
Выполняет: [[Участник:Kanast74|Дмитриева Анастасия]]

Статья:[[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(4)]]
Выполняют: [[Участник:F-morozov|Морозов Ф. В.]], [[Участник:Nataliya|Пащенко Н. Ф.]]

Статья:[[Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор]];
Выполняют: [[Участник:Trrufina|Третьякова Р.М.]] и [[Участник:Екатерина_Буторина|Буторина Е.В.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений2]];
Выполняет: [[Участник:Лукьянова Анна|Лукьянова А.Я.]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы]];
Выполняют: [[Участник: Galkina|Галкина А.С.]], [[Участник: Игорь|Плахов И.А.]]

Статья: [[Метод рекурсивной координатной бисекции]];
Выполняют: [[Участник: Obirvalger|Гордеев Михаил]], [[Участник: KolmakovEA|Колмаков Евгений]]

Статья: [[Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)]];
Выполняют: [[Участник: Эльвира Ахиярова|Ахиярова Эльвира]]

Статья: [[Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор]];
Выполняют: [[Участник: Janyell|Сычева Евгения]], [[Участник: Ahahalin|Хахалин Анатолий]]

Статья: [[Построение матрицы Адамара произвольного размера]];
Выполняют: [[Участник: Бугаков Юрий|Бугаков Юрий]], Кужамалиев Ернур

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки (1)]]
Выполняют: [[Участница:Sannikovats| Санникова Татьяна Сергеевна]], [[Участник:Plukshin| Лукшин Петр Андреевич]]

Статья: [[Алгоритм кластеризации, основанный на построении каркаса]];
Выполняют: [[Участник:SenderovichNikita| Сендерович Никита]]

Статья: [[Алгоритм кластеризации, основанный на максимизации ожидания]];
Выполняют: Готман Мария, Лукашкина Юлия

Статья: [[Partitioning_Around_Medoids_(PAM)]]
Выполняют: [[Участник:Avasilenko|А.Э.Василенко]], [[Участник:Anastasia|А.В.Тузикова]]

Статья: [[Нечеткий алгоритм С-средних (Fuzzy C-means)]]
Выполняют: [[Участник:Nikmedoed|Н.А. Муромцев]], [[Участник:illusive_mike|М.С. Дворецкий]]

Статья: [[Нечеткий алгоритм C средних]]
Выполняют: [[Участник:Gkhazeeva|Гелана Хазеева]], [[Участник:Yushin|Павел Юшин]]

Статья: [[Плотностный алгоритм кластеризации DBSCAN]]
Выполняют: [[Участник:Elena777mc|Малахова Е.С.]], [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]]

Статья: [[Кластеризация Partitioning Around Medoids (PAM)]]
Выполняют:[[ Участник:Тодуа Антон| Тодуа Антон]], [[Участник:Гусева Юлия| Гусева Юлия]]

Статья: [[Участник:Бугаков Юрий (613 группа), Кужамалиев Ернур (601 группа)/Построение матрицы Адамара произвольной размерности]]
Выполняют:[[ Участник:Бугаков Юрий| Бугаков Юрий]], [[Участник:Кужамалиев Ернур| Кужамалиев Ернур]]

Статья: [[Участник:Nikita/Построение_матрицы_Адамара|Построение матрицы Адамара]]
Выполняют: [[Участник:Nikita|Иванов Никита]], [[Участник:Tsyganov Nikita|Цыганов Никита]]

Статья: [[Метод Ньютона для решения систем нелинейных уравнений]]
Выполняют: [[Участник:Александр Чернышев|Александр Чернышев]], [[Участник:Захаров Никита|Захаров Никита]]

Статья: [[BIRCH|Сбалансированный итеративный алгоритм редукции и кластеризации с использованием иерархий
(BIRCH)]]
Выполняют: [[Участник:Светлана Морозова|Морозова Светлана]], [[Участник:Smirnov.maxim|Смирнов Максим]]

Статья: [[Плотностный_алгоритм_кластеризации|Плотностный_алгоритм_кластеризации]], Выполняют: [[Участник:Ramon93i7|Шемякин Роман]], [[Участник:Dadrik|Вашуров Илья]]

Статья: [[Алгоритм CLOPE кластеризации категориальных данных]].
Выполняют: [[Участник:Артем_Карпухин|Карпухин Артем]], [[Участник:Артем_Желтков|Желтков Артем]].

Статья: [[Участник:Борис/Алгоритм_Рунге-Кутты]]
Выполняет: [[Участник:Борис| Савков Борис]] и Степанов Евгений.

Статья: [[Алгоритм_кластеризации_категориальных_данных_CLOPE]].
Выполняют: [[Участник:Андрей_Туманов|А.Л.Туманов]], [[Участник:Александр_Александров|А.В.Александров]].

Статья: [[Алгоритм Ланцоша вычисления собственных значений симметричной матрицы для точной арифметики (без переортогонализации)]].
Выполняет: [[Участник:AleksLevin|А.Д.Левин]].

Статья: [[Быстрое дискретное преобразование Фурье (БПФ)]].
Выполняет: [[ Участник:Chachba.A| Чачба Алан]], [[Участник:Weasel| Костоев Руслан]].

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-16T22:11:21Z

Weasel: /* Масштабируемость алгоритма и его реализации */

{{Assignment}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы "разделяй и властвуй". Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math>-число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> - простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
Все запуски программы[http://pastebin.com/raw/xajKb9JN] проводились на с/к Blue Gene/P с использованием библиотеки Intel MKL.

IBM Blue Gene/P — массивно-параллельная вычислительная система, которая состоит из двух стоек, включающих 2048 четырехъядерных вычислительных узлов, с пиковой производительностью 27,9 терафлопс.

Характеристики системы:
* две стойки с вычислительными узлами и узлами ввода-вывода
* 1024 четырехъядерных вычислительных узла в каждой из стоек
* 16 узлов ввода-вывода в стойке (в текущей конфигурации активны 8, т.е. одна I/O-карта на 128 вычислительных узлов)
* программирование с использованием MPI, OpenMP/pthreads, POSIX I/O
* высокая энергоэффективность: ∼ 372 MFlops/W

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

Вычислительной узел:
* четыре микропроцессорных ядра PowerPC 450 (4-way SMP)
* пиковая производительность: 4 ядра x 3,4 GFlop/sec на ядро = 13,6 GFlop/sec
* пропускная способность памяти: 13,6 GB/sec
* 2 ГБ общей памяти
* 2 x 4 МБ кэш-памяти 2-го уровня (в документации по BG/P носит название L3)
* легковесное ядро (compute node kernel, CNK), представляющее собой Linux-подобную операционную систему, поддерживающую значительное подмножество Linux-совместимых системных вызовов
* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)
* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций

[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-16T22:10:07Z

Weasel:

{{Assignment}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы "разделяй и властвуй". Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math>-число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> - простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
Все запуски программы[http://pastebin.com/raw/xajKb9JN] проводились на с/к Blue Gene/P.

IBM Blue Gene/P — массивно-параллельная вычислительная система, которая состоит из двух стоек, включающих 2048 четырехъядерных вычислительных узлов, с пиковой производительностью 27,9 терафлопс.

Характеристики системы:
* две стойки с вычислительными узлами и узлами ввода-вывода
* 1024 четырехъядерных вычислительных узла в каждой из стоек
* 16 узлов ввода-вывода в стойке (в текущей конфигурации активны 8, т.е. одна I/O-карта на 128 вычислительных узлов)
* программирование с использованием MPI, OpenMP/pthreads, POSIX I/O
* высокая энергоэффективность: ∼ 372 MFlops/W

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

Вычислительной узел:
* четыре микропроцессорных ядра PowerPC 450 (4-way SMP)
* пиковая производительность: 4 ядра x 3,4 GFlop/sec на ядро = 13,6 GFlop/sec
* пропускная способность памяти: 13,6 GB/sec
* 2 ГБ общей памяти
* 2 x 4 МБ кэш-памяти 2-го уровня (в документации по BG/P носит название L3)
* легковесное ядро (compute node kernel, CNK), представляющее собой Linux-подобную операционную систему, поддерживающую значительное подмножество Linux-совместимых системных вызовов
* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)
* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций

[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Обсуждение участника:Chachba.A

2016-11-16T22:08:46Z

Weasel: /* Замечания к статье */

== Замечания к статье ==

* п.п. 1.8, 1.9 не раскрыты--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 14:57, 25 октября 2016 (MSK)
** исправлено
* не указан конкретный вклад каждого автора--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 14:57, 25 октября 2016 (MSK)
** исправлено
* в п.п. 2.4 следует добавить описание компьютерной платформы, текст исследуемой программы.--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 13:41, 16 ноября 2016 (MSK)
** сделано

== Замечания к статье "Быстрое дискретное преобразование Фурье" ==

* Перенесите пожалуйста статью в личное пространство [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** а как это сделать? У нас нет прав на это, похоже
* Раздел 1.1 - в самом первом абзаце стоит вставить обозначения двух фунций - f и f с крышкой, чтобы было ясно, что куда отображается. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* В общее описание алгоритма нужно вставить слова именно об алгоритме, а не только о математической задаче. В чем быстрота, за счет чего она достигается и т.д. Тут, в отличие от математического описания, не стоит увлекаться формулами. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Раздел 1.2 - существует обозначение части формулы через эпсилон, однако в следующей формуле он не встречается, странно. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Нужно пояснение, что происходит, когда N не представимо в виде произведения: применим ли алгоритм и в каких изменениях он нуждается. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Нет данных о глубине рекурсии, написать об этом явно, скорее всего, в разделе "вычислительное ядро алгоритма". [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-16T22:08:13Z

Weasel: /* Масштабируемость алгоритма и его реализации */

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы "разделяй и властвуй". Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math>-число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> - простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
Все запуски программы[http://pastebin.com/raw/xajKb9JN] проводились на с/к Blue Gene/P.

IBM Blue Gene/P — массивно-параллельная вычислительная система, которая состоит из двух стоек, включающих 2048 четырехъядерных вычислительных узлов, с пиковой производительностью 27,9 терафлопс.

Характеристики системы:
* две стойки с вычислительными узлами и узлами ввода-вывода
* 1024 четырехъядерных вычислительных узла в каждой из стоек
* 16 узлов ввода-вывода в стойке (в текущей конфигурации активны 8, т.е. одна I/O-карта на 128 вычислительных узлов)
* программирование с использованием MPI, OpenMP/pthreads, POSIX I/O
* высокая энергоэффективность: ∼ 372 MFlops/W

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

Вычислительной узел:
* четыре микропроцессорных ядра PowerPC 450 (4-way SMP)
* пиковая производительность: 4 ядра x 3,4 GFlop/sec на ядро = 13,6 GFlop/sec
* пропускная способность памяти: 13,6 GB/sec
* 2 ГБ общей памяти
* 2 x 4 МБ кэш-памяти 2-го уровня (в документации по BG/P носит название L3)
* легковесное ядро (compute node kernel, CNK), представляющее собой Linux-подобную операционную систему, поддерживающую значительное подмножество Linux-совместимых системных вызовов
* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)
* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций

[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-14T21:24:35Z

Weasel: /* Общее описание алгоритма */

{{Assignment}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы "разделяй и властвуй". Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math>-число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> - простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-14T20:59:59Z

Weasel:

{{Assignment}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы разделяй и властвуй. Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math>-число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> - простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Обсуждение участника:Chachba.A

2016-11-14T20:59:48Z

Weasel: /* Замечания к статье "Быстрое дискретное преобразование Фурье" */

== Замечания к статье ==

* п.п. 1.8, 1.9 не раскрыты--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 14:57, 25 октября 2016 (MSK)
** исправлено
* не указан конкретный вклад каждого автора--[[Участник:IgorS|IgorS]] ([[Обсуждение участника:IgorS|обсуждение]]) 14:57, 25 октября 2016 (MSK)
** исправлено

== Замечания к статье "Быстрое дискретное преобразование Фурье" ==

* Перенесите пожалуйста статью в личное пространство [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** а как это сделать?
* Раздел 1.1 - в самом первом абзаце стоит вставить обозначения двух фунций - f и f с крышкой, чтобы было ясно, что куда отображается. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* В общее описание алгоритма нужно вставить слова именно об алгоритме, а не только о математической задаче. В чем быстрота, за счет чего она достигается и т.д. Тут, в отличие от математического описания, не стоит увлекаться формулами. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Раздел 1.2 - существует обозначение части формулы через эпсилон, однако в следующей формуле он не встречается, странно. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Нужно пояснение, что происходит, когда N не представимо в виде произведения: применим ли алгоритм и в каких изменениях он нуждается. [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done
* Нет данных о глубине рекурсии, написать об этом явно, скорее всего, в разделе "вычислительное ядро алгоритма". [[Участник:Kronberg|Kronberg]] ([[Обсуждение участника:Kronberg|обсуждение]]) 13:31, 11 ноября 2016 (MSK)
** Done

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-14T20:59:18Z

Weasel:

{{Assignment|IgorS}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы разделяй и властвуй. Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math>-число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> - простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-14T20:05:39Z

Weasel: /* Масштабируемость алгоритма и его реализации */

{{Assignment|IgorS}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==
[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Вкипедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-28T12:00:20Z

Weasel:

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-26T14:47:31Z

Weasel:

Обсуждение участника:Chachba.A

2016-10-26T14:45:12Z

Weasel: /* Замечания к статье */

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-26T14:44:43Z

Weasel:

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-26T14:43:44Z

Weasel:

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]] Чачба А.Н. заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, Костоев Р.С. написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Вкипедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-26T14:32:42Z

Weasel: /* Входные и выходные данные алгоритма */

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Вкипедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-26T14:07:35Z

Weasel: /* Ресурс параллелизма алгоритма */

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа $N$ близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

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

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексым полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору.
'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Вкипедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-15T10:51:07Z

Weasel: /* Литература */

{{Assignment}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
Пусть имеется неограниченное число процессоров, тогда учитывая схему алгоритма БПФ, максимальное число одновременно работающих процессоров может составлять <math>N</math>, тогда сложность алгоритма на <math>N</math> процессорах составит <math>\log{N}</math>.

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексым полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору.
'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Вкипедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-15T10:50:50Z

Weasel:

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-15T10:41:57Z

Weasel:

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-15T10:23:58Z

Weasel: /* Вычислительное ядро алгоритма */

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
Пусть имеется неограниченное число процессоров, тогда учитывая схему алгоритма БПФ, максимальное число одновременно работающих процессоров может составлять <math>N</math>, тогда сложность алгоритма на <math>N</math> процессорах составит <math>\log{N}</math>.

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексым полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору.
'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-15T10:12:50Z

Weasel: /* Существующие реализации алгоритма */

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>O(N{k})</math> уровней рекурсии, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
Пусть имеется неограниченное число процессоров, тогда учитывая схему алгоритма БПФ, максимальное число одновременно работающих процессоров может составлять <math>N</math>, тогда сложность алгоритма на <math>N</math> процессорах составит <math>\log{N}</math>.

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексым полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору.
'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-14T16:19:37Z

Weasel: /* Свойства алгоритма */

Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

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

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего <math>N</math> отсчетов.
Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>O(N{k})</math> уровней рекурсии, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
Пусть имеется неограниченное число процессоров, тогда учитывая схему алгоритма БПФ, максимальное число одновременно работающих процессоров может составлять <math>N</math>, тогда сложность алгоритма на <math>N</math> процессорах составит <math>\log{N}</math>.

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексым полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору.
'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

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

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

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

= Литература =

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-14T12:04:59Z

Weasel: /* Макроструктура алгоритма */

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-14T11:57:40Z

Weasel: /* Вычислительное ядро алгоритма */

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-14T11:54:27Z

Weasel: /* Вычислительное ядро алгоритма */

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-14T11:30:46Z

Weasel: /* Информационный граф */

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-14T11:13:23Z

Weasel:

Быстрое дискретное преобразование Фурье (БПФ)

2016-10-12T20:39:43Z

Weasel: