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

Kronberg в 14:09, 29 ноября 2016

2016-11-29T14:09:45Z

← Предыдущая версия		Версия от 14:09, 29 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|IgorS}}		{{Assignment\|IgorS\|Kronberg}}

	{{algorithm		{{algorithm

IgorS в 13:03, 22 ноября 2016

2016-11-22T13:03:18Z

← Предыдущая версия		Версия от 13:03, 22 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|IgorS}}		{{Assignment\|IgorS}}
	~~{{Assignment}}~~
	{{algorithm		{{algorithm
	\| name = Алгоритм одномерного преобразования Фурье для действительных чисел		\| name = Алгоритм одномерного преобразования Фурье для действительных чисел

Ivanov.kir.m в 11:30, 22 ноября 2016

2016-11-22T11:30:07Z

← Предыдущая версия		Версия от 11:30, 22 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|IgorS}}		{{Assignment\|IgorS}}
			{{Assignment}}
	{{algorithm		{{algorithm
	\| name = Алгоритм одномерного преобразования Фурье для действительных чисел		\| name = Алгоритм одномерного преобразования Фурье для действительных чисел

Kronberg: /* Рекурсивное описание */

2016-11-18T09:28:37Z

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

← Предыдущая версия		Версия от 09:28, 18 ноября 2016
Строка 70:		Строка 70:
	'''Замечание:''' Как правило все ''поворотные множители'' вычисляются заранее и хранятся в специальном массиве.		'''Замечание:''' Как правило все ''поворотные множители'' вычисляются заранее и хранятся в специальном массиве.

	'''Замечание:''' В общем случае <math>N</math> разбивается на <math>n_1 \cdot n_2</math> так, чтобы <math>n_1</math> и <math>n_2</math> сами не являлись простыми числами и разлагались на множители не являющиеся простыми числами.		'''Замечание:''' В общем случае <math>N</math> разбивается на <math>n_1 \cdot n_2</math> так, чтобы <math>n_1</math> и <math>n_2</math> сами не являлись простыми числами и разлагались на множители, не являющиеся простыми числами.

	'''Замечание:''' В случае простого <math>N</math> оно дополняется(как правило ~~единицией~~) до ~~непростого~~ числа. В процессе слияния добавленные значения отбрасываются.		'''Замечание:''' В случае простого <math>N</math> оно дополняется(как правило единицей) до составного числа. В процессе слияния добавленные значения отбрасываются.

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

Kronberg: /* Математическое описание алгоритма */

2016-11-18T09:28:03Z

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

← Предыдущая версия		Версия от 09:28, 18 ноября 2016
Строка 66:		Строка 66:
	# К каждой строке матрицы <math>A^T</math> применяется БПФ порядка <math>n_2</math>		# К каждой строке матрицы <math>A^T</math> применяется БПФ порядка <math>n_2</math>

	Так как алгоритм реализует принцип ~~"разделяй~~ и ~~властвуй"~~ глубина рекурсии составляет <math>O (\log N)</math> от числа входных элементов.		Так как алгоритм реализует принцип «разделяй и властвуй», глубина рекурсии составляет <math>O (\log N)</math> от числа входных элементов.

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

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

2016-11-18T09:23:53Z

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

← Предыдущая версия		Версия от 09:23, 18 ноября 2016
Строка 24:		Строка 24:
	</math>		</math>

	В отличие от своего классического аналога, БПФ имеет сложность <math>O(N\log{N})</math>, а не <math>O(N^2)</math>, это достигается благодаря разделению исходного вектора на несколько частей так, чтобы, применив к этим частям БПФ и объединив результаты путем умножения на поворотные множители и дополнительного БПФ, можно было получить преобразование Фурье исходного вектора - принцип «разделяй и властвуй».		В отличие от своего классического аналога, БПФ имеет сложность <math>O(N\log{N})</math>, а не <math>O(N^2)</math>, это достигается благодаря разделению исходного вектора на несколько частей так, чтобы, применив к этим частям БПФ и объединив результаты путем умножения на поворотные множители и дополнительного БПФ, можно было получить преобразование Фурье исходного вектора — принцип «разделяй и властвуй».

	Область применения данного метода простирается от обработки аудио информации до собственно спектрального анализа.		Область применения данного метода простирается от обработки аудио информации до собственно спектрального анализа.

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

2016-11-18T09:22:37Z

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

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

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	'''Быстрое дискретное преобразование Фурье''' (''БПФ'') - популярный в современном мире математический метод преобразования вектора/матрицы комплексных/действительных чисел - ''сигнала'' - в вектор/матрицу комплексных чисел - ''спектр''. С математической точки зрения преобразование сигнала <math>s</math> (как функции по времени <math>t</math>) в спектр <math>\hat{s}</math> описывается формулой		'''Быстрое дискретное преобразование Фурье''' (''БПФ'') - популярный в современном мире математический метод преобразования вектора/матрицы комплексных/действительных чисел — ''сигнала'' — в вектор/матрицу комплексных чисел — ''спектр''. С математической точки зрения преобразование сигнала <math>s</math> (как функции по времени <math>t</math>) в спектр <math>\hat{s}</math> описывается формулой
	:<math>		:<math>
	\hat{s}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}s(t)e^{-it\omega}\,dt		\hat{s}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}s(t)e^{-it\omega}\,dt
	</math>		</math>

	В ~~отличии~~ от своего классического аналога БПФ имеет сложность <math>O(N\log{N})</math>, а не <math>O(N^2)</math>, это достигается благодаря разделению исходного вектора на несколько частей, ~~так~~ чтобы применив к этим частям БПФ и объединив результаты путем умножения на поворотные множители и дополнительного БПФ, можно было получить преобразование Фурье исходного вектора - принцип ~~"разделяй~~ и ~~властвуй"~~.		В отличие от своего классического аналога, БПФ имеет сложность <math>O(N\log{N})</math>, а не <math>O(N^2)</math>, это достигается благодаря разделению исходного вектора на несколько частей так, чтобы, применив к этим частям БПФ и объединив результаты путем умножения на поворотные множители и дополнительного БПФ, можно было получить преобразование Фурье исходного вектора - принцип «разделяй и властвуй».

	Область применения данного метода простирается от обработки аудио информации до собственно спектрального анализа.		Область применения данного метода простирается от обработки аудио информации до собственно спектрального анализа.
Строка 30:		Строка 30:


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

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

IgorS в 09:33, 17 ноября 2016

2016-11-17T09:33:46Z

← Предыдущая версия		Версия от 09:33, 17 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|IgorS}}
	{{algorithm		{{algorithm
	\| name = Алгоритм одномерного преобразования Фурье для действительных чисел		\| name = Алгоритм одномерного преобразования Фурье для действительных чисел

Ivanov.kir.m в 12:41, 16 ноября 2016

2016-11-16T12:41:04Z

← Предыдущая версия		Версия от 12:41, 16 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	{{algorithm		{{algorithm
	\| name = Алгоритм одномерного преобразования Фурье для действительных чисел		\| name = Алгоритм одномерного преобразования Фурье для действительных чисел

Ivanov.kir.m: /* Описание платформы IBM Blue Gene/P */

2016-11-16T12:33:50Z

Описание платформы IBM Blue Gene/P

← Предыдущая версия		Версия от 12:33, 16 ноября 2016
Строка 231:		Строка 231:
	* кэш предвыборки (L2 prefetch): 14 потоков предварительной выборки (stream prefetching): 14 x 256 байтов		* кэш предвыборки (L2 prefetch): 14 потоков предварительной выборки (stream prefetching): 14 x 256 байтов
	* два блока 64-битной арифметики с плавающей точкой (Floating Point Unit, FPU), каждый из которых может выдавать за один такт результат совмещенной операции умножения-сложения (Fused Multiply-Add, FMA)		* два блока 64-битной арифметики с плавающей точкой (Floating Point Unit, FPU), каждый из которых может выдавать за один такт результат совмещенной операции умножения-сложения (Fused Multiply-Add, FMA)
	пиковая производительность: 2 FPU x 2 FMA x 850 MHz = 3,4 GFlop/sec per core		* пиковая производительность: 2 FPU x 2 FMA x 850 MHz = 3,4 GFlop/sec per core

	Вычислительные узлы и I/O-карты в аппаратном смысле неразличимы и являются взаимозаменяемыми, разница между ними состоит лишь в способе их использования. У них нет локальной файловой системы, поэтому все операции ввода-вывода перенаправляются внешним устройствам.		Вычислительные узлы и I/O-карты в аппаратном смысле неразличимы и являются взаимозаменяемыми, разница между ними состоит лишь в способе их использования. У них нет локальной файловой системы, поэтому все операции ввода-вывода перенаправляются внешним устройствам.
Строка 245:		Строка 245:
	* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)		* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)
	* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций		* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций


	=== Оценка масштабируемости алгоритма ===		=== Оценка масштабируемости алгоритма ===