Алгоритм Ку́ли — Тью́ки — наиболее часто используемый алгоритм вычисления быстрого преобразования Фурье. Алгоритм позволяет выразить дискретное преобразование Фурье длины, равной произвольному составному числу , через определённое количество преобразований меньшей длины с помощью рекурсии, понижая таким образом сложность вычислений до для гладких . Назван в честь и Дж. Тьюки.
Основной алгоритм
Для произвольного натурального числа дискретным преобразованием Фурье комплексного вектора , где , называется комплексный вектор , где , компоненты которого задаются формулой
где .
Для построения алгоритма делается предположение, что для некоторых натуральных и и производится следующая замена индексов:
в результате которой получается
Далее векторы входных и выходных данных преобразуются в двумерные массивы и , задающиеся равенствами
Стоит заметить, что компоненты упорядочены не так, как компоненты .
Далее пусть и . Очевидно, что . Тогда в терминах двумерных переменных формула преобразуется к виду
Таким образом, вычисление преобразования длины сводится к выполнению следующих действий: Вычисление преобразований длины . Умножение на комплексные «поворачивающие» множители. Вычисление преобразований длины . При этом вместо комплексных сложений и комплексных умножений исходной формулы итоговая схема содержит не более комплексных сложений и комплексных умножений.
Каждое из преобразований длины или можно вычислять с помощью различных быстрых алгоритмов, в частности, снова по вышеприведённой схеме. В этом случае преобразование длины может быть представлено в форме, требующей выполнения комплексных умножений.
Алгоритм по основанию два Во многих приложениях длина преобразования равна степени двойки: . Тогда в вышеприведённой схеме возможны варианты или . В этом случае говорят об алгоритме Кули — Тьюки по основанию два ().
Если , то говорят об алгоритме Кули — Тьюки с прореживанием по времени. В этом случае уравнения преобразуются к виду
Если ввести обозначения и , то уравнения можно переписать как
Такая операция обычно называется «бабочкой».
Данная процедура может быть применена к входному вектору рекурсивно. На каждом шаге -точечное преобразование разбивается на два -точечных преобразования, которые, в свою очередь, разбиваются таким же образом до тех пор, пока длина преобразования не станет равна единице. Затем происходит обратный ход, на каждом шаге длины результатов преобразований удваиваются с помощью «бабочек». При такой реализации выполняется комплексных умножений и комплексных сложений.
Этот процесс является примером применения методики «разделяй и властвуй». При этом во многих реализациях прямой рекурсии избегают и вместо неё дерево вычислений проходится в порядке поиска в ширину.
Если , то говорят об алгоритме Кули — Тьюки с прореживанием по частоте. В этом случае уравнения преобразуются к виду
Алгоритм Рейдера — Бреннера Пусть
и пусть
С использованием формул алгоритма с прореживанием по частоте нетрудно убедиться, что выполняется следующее соотношение:
Такая модификация алгоритма по основанию два называется алгоритмом Рейдера — Бреннера. Она позволяет уменьшить вычислительную сложность за счёт более простых умножений на чисто мнимые константы . Аналогичные формулы можно получить с использованием вещественных констант .
История Алгоритм и его рекурсивная реализация были изобретены около 1805 года К. Гауссом при интерполировании траекторий астероидов Паллада и Юнона. Тогда открытие не получило широкого распространения и было опубликовано лишь после смерти учёного на новой латыни. Результат Гаусса несколько раз переоткрывался в различных формах в течение последующих 150 лет и стал популярным после публикации в 1965 году статьи из IBM и Дж. Тьюки из Принстона, в которой алгоритм был в очередной раз переоткрыт, а также описывалась удобная реализация для ЭВМ.
Тот факт, что первооткрывателем алгоритма является Гаусс, был обнаружен лишь через несколько лет после публикации Кули и Тьюки. В своей статье они ссылались только на работу И. Дж. Гуда, в которой был описан алгоритм Гуда — Томаса.
Выражение преобразования Фурье длины через два преобразования длины иногда называют леммой — Ланцоша, так как оно было получено этими двумя авторами в 1942 году.
Примечания
Литература
См. также Алгоритм Блуштайна
Категория:Преобразование Фурье Категория:Алгоритмы