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

IgorS в 07:59, 26 декабря 2016

2016-12-26T07:59:33Z

← Предыдущая версия		Версия от 07:59, 26 декабря 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

	{{algorithm		{{algorithm

Timokhinivan в 06:10, 15 декабря 2016

2016-12-15T06:10:03Z

← Предыдущая версия		Версия от 06:10, 15 декабря 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm

IgorS в 07:21, 5 декабря 2016

2016-12-05T07:21:38Z

← Предыдущая версия		Версия от 07:21, 5 декабря 2016
Строка 1:		Строка 1:
	~~{{Assignment\|Kronberg}}~~

	{{algorithm		{{algorithm

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

2016-11-29T14:16:43Z

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

	{{algorithm		{{algorithm

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

2016-11-26T11:30:55Z

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

← Предыдущая версия		Версия от 11:30, 26 ноября 2016
Строка 282:		Строка 282:
	В общем, можно заметить, что, если возникла необходимость вычислять преобразование Фурье параллельно, добавление вычислительных узлов является целесообразным, однако такой ситуации следует по возможности избегать, поскольку ресурсы параллельной системы при этом расходуются крайне неэффективно.		В общем, можно заметить, что, если возникла необходимость вычислять преобразование Фурье параллельно, добавление вычислительных узлов является целесообразным, однако такой ситуации следует по возможности избегать, поскольку ресурсы параллельной системы при этом расходуются крайне неэффективно.

	При измерениях использовалась реализация алгоритма, имеющаяся в библиотеке Intel® MKL, расчёты проводились на суперкомпьютере «Ломоносов».		При измерениях использовалась реализация алгоритма, имеющаяся в библиотеке Intel® MKL, расчёты проводились на суперкомпьютере «Ломоносов». Код доступен [https://bitbucket.org/timokhin_ivan/fft/src здесь].

	=== Динамические характеристики и особенности реализации алгоритма ===		=== Динамические характеристики и особенности реализации алгоритма ===

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

2016-11-18T20:52:17Z

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

← Предыдущая версия		Версия от 20:52, 18 ноября 2016
Строка 282:		Строка 282:
	В общем, можно заметить, что, если возникла необходимость вычислять преобразование Фурье параллельно, добавление вычислительных узлов является целесообразным, однако такой ситуации следует по возможности избегать, поскольку ресурсы параллельной системы при этом расходуются крайне неэффективно.		В общем, можно заметить, что, если возникла необходимость вычислять преобразование Фурье параллельно, добавление вычислительных узлов является целесообразным, однако такой ситуации следует по возможности избегать, поскольку ресурсы параллельной системы при этом расходуются крайне неэффективно.

	При измерениях использовалась реализация алгоритма, имеющаяся в библиотеке Intel® MKL.		При измерениях использовалась реализация алгоритма, имеющаяся в библиотеке Intel® MKL, расчёты проводились на суперкомпьютере «Ломоносов».

	=== Динамические характеристики и особенности реализации алгоритма ===		=== Динамические характеристики и особенности реализации алгоритма ===

IgorS в 10:43, 16 ноября 2016

2016-11-16T10:43:43Z

← Предыдущая версия		Версия от 10:43, 16 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|IgorS}}~~
	{{algorithm		{{algorithm
	\| name = Быстрое преобразование Фурье		\| name = Быстрое преобразование Фурье

Timokhinivan: /* Сведение к (почти) двумерному преобразованию (алгоритм Кули-Тьюки) */

2016-11-15T16:11:13Z

Сведение к (почти) двумерному преобразованию (алгоритм Кули-Тьюки)

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

	Так, если <math>N = \prod_{i=1}^{K} p_i</math>, то целесообразно		Так, если <math>N = \prod_{i=1}^{K} p_i</math>, то целесообразно
	на каждом уровне рекурсии «отщеплять» одно <math>p_i</math>. В этом		на каждом уровне рекурсии «отщеплять» одно <math>p_i</math> (уровней рекурсии при этом будет <math>K \sim \log N</math>). В этом
	случае задача сводится к вычислению <math> \prod_{i\neq j} p_i </math>		случае задача сводится к вычислению <math> \prod_{i\neq j} p_i </math>
	преобразований Фурье порядка <math>p_j</math> для всех		преобразований Фурье порядка <math>p_j</math> для всех

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

2016-11-15T16:09:25Z

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

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

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	~~Преобразование~~ Фурье ~~переводит сигнал в его спектр и обратно~~, ~~и широко~~		В общем случае многомерное преобразование Фурье соответствует умножению на матрицу преобразования по каждой из координат, что для массива данных <math>N_1\times N_2 \times \cdots \times N_m</math> означает выполнение <math>\sum_{i=1}^m \prod_{k\neq i} N_k</math> одномерных преобразований. Ключевым наблюдением, приводящим к быстрому алгоримту для вычисления преобразования, является возможность свести (с некоторыми оговорками) одномерное преобразование к двумерному, которое для <math>N = mn</math> требует <math>m + n</math> рекурсивных вызовов, что, при применении такого метода на всех уровнях рекурсии, даёт общую сложность алгоритма <math>O(N \log N)</math>.
	~~применяется в самых различных областях вычислительной математики —~~
	~~собственно спектральный анализ, сжатие~~ данных~~, вычисление свёрток и~~
	т.~~д. В связи с этим~~, ~~особый интерес представляют быстрые алгоритмы~~ для
	вычисления ~~этого~~ преобразования~~. На сегодняшний день наилучшие из~~
	~~них имеют~~ сложность <math>O(n \log n)</math>.

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

Timokhinivan: /* Математическое описание алгоритма */ Объяснение понятия «порядок преобразования»

2016-11-15T15:51:57Z

Математическое описание алгоритма: Объяснение понятия «порядок преобразования»

← Предыдущая версия		Версия от 15:51, 15 ноября 2016
Строка 27:		Строка 27:
	</math>		</math>
	где <math>\epsilon_N = e^{-\frac{2i\pi}{N}}</math> — первообразный корень		где <math>\epsilon_N = e^{-\frac{2i\pi}{N}}</math> — первообразный корень
	из 1 степени <math>N</math> (т.е. <math>\epsilon_N</math> является корнем из 1 степени <math>N</math>, но не является корнем никакой меньшей степени).		из 1 степени <math>N</math> (т.е. <math>\epsilon_N</math> является корнем из 1 степени <math>N</math>, но не является корнем никакой меньшей степени). Число <math>N</math> при этом называется порядком преобразования.

	Таким образом, преобразование Фурье является линейным и задаётся		Таким образом, преобразование Фурье является линейным и задаётся