Алгоритм Кули — Тьюки
Алгоритм Ку́ли — Тью́ки — наиболее часто используемый алгоритм вычисления быстрого преобразования Фурье. Алгоритм позволяет выразить дискретное преобразование Фурье длины, равной произвольному составному числу , через определённое количество преобразований меньшей длины с помощью рекурсии, понижая таким образом сложность вычислений до для гладких . Назван в честь Дж. Кули и Дж. Тьюки.
Основной алгоритм
Для произвольного натурального числа дискретным преобразованием Фурье комплексного вектора , где , называется комплексный вектор , где , компоненты которого задаются формулой
где .
Для построения алгоритма делается предположение, что для некоторых натуральных и и производится следующая замена индексов[1]:
в результате которой получается
Далее векторы входных и выходных данных преобразуются в двумерные массивы и , задающиеся равенствами
Стоит заметить, что компоненты упорядочены не так, как компоненты .
Далее пусть и . Очевидно, что . Тогда в терминах двумерных переменных формула преобразуется к виду[2]
Таким образом, вычисление преобразования длины сводится к выполнению следующих действий:
- Вычисление преобразований длины .
- Умножение на комплексные «поворачивающие» множители.
- Вычисление преобразований длины .
При этом вместо комплексных сложений и комплексных умножений исходной формулы итоговая схема содержит не более комплексных сложений и комплексных умножений[2].
Каждое из преобразований длины или можно вычислять с помощью различных быстрых алгоритмов, в частности, снова по вышеприведённой схеме. В этом случае преобразование длины может быть представлено в форме, требующей выполнения комплексных умножений[3].
Алгоритм по основанию два
Во многих приложениях длина преобразования равна степени двойки: . Тогда в вышеприведённой схеме возможны варианты или . В этом случае говорят об алгоритме Кули — Тьюки по основанию два[3] (англ. radix-2).
Если , то говорят об алгоритме Кули — Тьюки с прореживанием по времени[3]. В этом случае уравнения преобразуются к виду
Если ввести обозначения и , то уравнения можно переписать как
Такая операция обычно называется «бабочкой».
Данная процедура может быть применена к входному вектору рекурсивно. На каждом шаге -точечное преобразование разбивается на два -точечных преобразования, которые, в свою очередь, разбиваются таким же образом до тех пор, пока длина преобразования не станет равна единице. Затем происходит обратный ход, на каждом шаге длины результатов преобразований удваиваются с помощью «бабочек». При такой реализации выполняется комплексных умножений и комплексных сложений.
Этот процесс является примером применения методики «разделяй и властвуй». При этом во многих реализациях прямой рекурсии избегают и вместо неё дерево вычислений проходится в порядке поиска в ширину.
Если , то говорят об алгоритме Кули — Тьюки с прореживанием по частоте[4]. В этом случае уравнения преобразуются к виду
Алгоритм Рейдера — Бреннера
Пусть
и пусть
С использованием формул алгоритма с прореживанием по частоте нетрудно убедиться, что выполняется следующее соотношение:
Такая модификация алгоритма по основанию два называется алгоритмом Рейдера — Бреннера. Она позволяет уменьшить вычислительную сложность за счёт более простых умножений на чисто мнимые константы [5]. Аналогичные формулы можно получить с использованием вещественных констант [6].
История
Алгоритм и его рекурсивная реализация были изобретены около 1805 года К. Гауссом при интерполировании траекторий астероидов Паллада и Юнона[7]. Тогда открытие не получило широкого распространения и было опубликовано лишь после смерти учёного на новой латыни. Результат Гаусса несколько раз переоткрывался в различных формах в течение последующих 150 лет и стал популярным после публикации в 1965 году статьи Дж. Кули из IBM и Дж. Тьюки из Принстона, в которой алгоритм был в очередной раз переоткрыт, а также описывалась удобная реализация для ЭВМ[8].
Тот факт, что первооткрывателем алгоритма является Гаусс, был обнаружен лишь через несколько лет после публикации Кули и Тьюки. В своей статье они ссылались только на работу И. Дж. Гуда, в которой был описан алгоритм Гуда — Томаса.
Выражение преобразования Фурье длины через два преобразования длины иногда называют леммой Дэниэльсона — Ланцоша, так как оно было получено этими двумя авторами в 1942 году[9].
Примечания
- Блейхут, 1989, с. 129.
- Блейхут, 1989, с. 130.
- Блейхут, 1989, с. 133.
- Блейхут, 1989, с. 134.
- Блейхут, 1989, с. 138.
- Нуссбаумер, 1985, с. 92.
- Heideman, M. T., Johnson, D. H., Burrus, C. S. Gauss and the history of the fast Fourier transform (англ.) // IEEE ASSP Magazine. — IEEE, 1984. — Vol. 1, iss. 4. — P. 14—21. — doi:10.1109/MASSP.1984.1162257.
- Cooley, J. W., Tukey, J. W. An algorithm for the machine calculation of complex Fourier series (англ.) // Mathematics of Computation. — 1965. — Vol. 19. — P. 297—301. — doi:10.1090/S0025-5718-1965-0178586-1.
- Danielson, G. C., Lanczos, C. Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids (англ.) // Journal of the Franklin Institute. — 1942. — Vol. 233, iss. 4. — P. 365–380. — doi:10.1016/S0016-0032(42)90767-1.