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

Kronberg в 07:52, 12 декабря 2016

2016-12-12T07:52:50Z

← Предыдущая версия		Версия от 07:52, 12 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|IgorS}}		{{Assignment\|IgorS\|Kronberg}}
	Авторы: [[Участник:Chachba.A\|Чачба А.Н.]], [[Участник:Weasel\|Костоев Р.С.]]		Авторы: [[Участник:Chachba.A\|Чачба А.Н.]], [[Участник:Weasel\|Костоев Р.С.]]

AntonChupin в 08:33, 21 ноября 2016

2016-11-21T08:33:35Z

← Предыдущая версия		Версия от 08:33, 21 ноября 2016
Строка 105:		Строка 105:
	''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.		''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

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

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

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

2016-11-20T22:36:06Z

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

← Предыдущая версия		Версия от 22:36, 20 ноября 2016
Строка 44:		Строка 44:
	В общем же случае, когда <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 = \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</math> не факторизуется в произведение простых множителей (то есть <math>N</math> — простое число), то данный алгоритм напрямую не применим. На замену ему приходит алгоритм Радера, который в некотором смысле сводит задачу размерности <math>N</math> к подзадаче задаче размерности <math>N\pm 1</math> вычисления свертки, в которой допустимо и увеличение размерности до составных в том числе.

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

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

2016-11-18T09:39:24Z

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

← Предыдущая версия		Версия от 09:39, 18 ноября 2016
Строка 42:		Строка 42:
	В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</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 = \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</math> не факторизуется в произведение простых множителей (то есть <math>N</math> — простое число), то данный алгоритм не применим. На замену ему приходит алгоритм Радера, имеющий худшую асимптотику, нежели обычный БПФ, но лучшую чем <math>O(N^2)</math>. Также алгоритм Радера потребует дополнительного взаимодействия процессоров, что приведет к ухудшению эффективности.

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

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

2016-11-18T09:35:39Z

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

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

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

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

2016-11-18T09:34:29Z

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

← Предыдущая версия		Версия от 09:34, 18 ноября 2016
Строка 16:		Строка 16:

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

	:<math>		:<math>

IgorS в 10:57, 17 ноября 2016

2016-11-17T10:57:12Z

← Предыдущая версия		Версия от 10:57, 17 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|IgorS}}
	Авторы: [[Участник:Chachba.A\|Чачба А.Н.]], [[Участник:Weasel\|Костоев Р.С.]]		Авторы: [[Участник:Chachba.A\|Чачба А.Н.]], [[Участник:Weasel\|Костоев Р.С.]]

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

2016-11-16T22:11:21Z

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

← Предыдущая версия		Версия от 22:11, 16 ноября 2016
Строка 144:		Строка 144:

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

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

Weasel в 22:10, 16 ноября 2016

2016-11-16T22:10:07Z

← Предыдущая версия		Версия от 22:10, 16 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	Авторы: [[Участник:Chachba.A\|Чачба А.Н.]], [[Участник:Weasel\|Костоев Р.С.]]		Авторы: [[Участник:Chachba.A\|Чачба А.Н.]], [[Участник:Weasel\|Костоев Р.С.]]

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

2016-11-16T22:08:13Z

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

← Предыдущая версия		Версия от 22:08, 16 ноября 2016
Строка 144:		Строка 144:

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

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