7.2. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Очевидно, что преобразование Фурье вектора а из и обратное к нему можно вычислить за время в предположении, что каждая арифметическая операция над элементами кольца выполняется за один шаг. Однако если я — степень числа 2, то можно сделать это быстрее: известен алгоритм сложности вычисляющий преобразование Фурье или обратное к нему, и мы думаем, что эта оценка неулучшаема. Приведем только алгоритм прямого преобразования Фурье. Алгоритм обратного преобразования аналогичен и предоставляется читателю. Основная идея быстрого преобразования Фурье (БПФ) является по своей природе алгебраической; мы находим подобие между частями тех сумм, которые порождаются умножением Во всем этом разделе мы считаем, что для некоторого целого числа

Вспомним, что вычисление вектора а эквивалентно вычислению полинома в точках Но вычисление в точке равносильно нахождению остатка от деления на (Чтобы увидеть это, можно записать в виде где с — постоянная. Тогда Таким образом, вычисление преобразования Фурье сводится к нахождению остатка от деления полинома степени на каждый из полиномов

Обычное последовательное деление на каждый из полиномов дает процесс сложности Чтобы построить более быстрый алгоритм, перемножим попарно затем перемножим попарно получившиеся полиномов и т. д., пока не останется два полинома каждый из которых равен произведению половины полиномов Далее делим на Соответствующие остатки имеют степень не более каждый. Для каждого корня со, для которого делится без остатка на нахождение остатка от деления на равносильно нахождению остатка от деления на Аналогичное утверждение верно для каждого корня со, для которого делится без остатка на Поэтому вычисление остатков от деления на каждый из полиномов равносильно вычислению остатков от деления на каждый из подходящих полиномов Рекурсивное применение этой тактики "разделяй и властвуй" гораздо эффективнее прямолинейного метода деления на каждый полином .

При перемножении полиномов можно ожидать, что произведения будут содержать результаты перекрестных умножений одночленов. Однако при подходящем упорядочении полиномов

можно добиться, чтобы все произведения имели вид и это еще уменьшит время, затрачиваемое на умножения и деления полиномов. Изложим все эти идеи точнее.

Пусть перестановка элементов которую мы конкретизируем позже. Определим полиномы где является целым кратным числа

Таким образом, и в общем случае

Существует полиномов со вторым нижним индексом и каждый полином делит в точности один из них. Полиномы изображены на рис. 7.1. (См. также разд. 8.4 и 8.5.)

Наша цель — вычислить остаток от деления на для каждого Для этого вычислим остатки от деления на для каждого начиная с и кончая

Допустим, что уже вычислены полиномы степени остающиеся от деления на (Можно считать, что Поскольку где мы утверждаем, что остаток от деления на равен остатку от деления на и аналогичное утверждение верно и для Для

Рис. 7.1. Полиномы

доказательства положим

где степень полинома не превосходит Так как

то

Разделим обе части равенства (7.5) на так как делятся без остатка, то остаток от деления на равен

Таким образом, можно получить остатки от деления на на разделив на полином степени а не полином степени 2—1. Этот метод выполнения делений сам по себе дает экономию времени. Но можно делать еще больше. Выбрав подходящий порядок элементов для степеней со, можно добиться, чтобы каждый полином имел вид при некотором Деление на такие полиномы выполняется особенно просто.

Лемма 7.2. Пусть и со — примитивный корень степени из единицы. Пусть двоичное представление целого числа где целое число с двоичным представлением Обозначим Тогда

Доказательство. Доказательство проводится индукцией по Базис, т. е. случай тривиален, ибо по определению Для проведения шага индукции заметим, что при

где четное число между и 2—1. Тогда

поскольку Следовательно,

поскольку

Пример 7.1. Если то список есть . Полиномы иллюстрируются на рис. 7.2.

Рис. 7.2. Полиномы из леммы 7.2.

Покажем, как использовать полиномы для вычисления остатков. Вначале вычисляются остатки от деления на на где Затем вычисляются остатки от деления на на и остатки от деления на на Наконец, вычисляются где остатки от деления на на остатки от деления на на

Другие примеры применения этого подхода приведены в разд. 8.5.

Доказав, что полиномы имеют вид покажем, что остаток от деления на найти легко.

Лемма 7.3. Пусть

и с — постоянная. Тогда остаток от деления на равен

Доказательство. Достаточно заметить, что можно представить в виде

Итак, остаток от деления произвольного полинома степени на можно найти за шагов. Любой из известных

Рис. 7.3. (см. скан) Алгоритм быстрого преобразования Фурье.

алгоритмов тратит больше времени на вычисление остатка от деления произвольного полинома степени на произвольный полином степени

Сформулируем полностью БПФ-алгоритм.

Алгоритм 7.1. Быстрое преобразование Фурье

Вход. Вектор где для некоторого целого числа

Выход. Вектор где для

Метод. См. рис. 7.3.

Модификация алгоритма 7.1 для вычисления обратных преобразований состоит в замене со на этого в строках 6 и 7 меняются знаки показателей степеней элемента Кроме того, в строке делится на

Пример 7.2. Пусть значит, При цикл в строках 3—7 выполняется только для В строке в строке в строках 6 и 7

и

Если то I принимает значения и 4. Когда в строке Тогда в строках 6 и 7

и

Когда в строке В силу строк 6 и 7 и формулы для приведенной выше,

Наконец, если то I принимает значения 0, 2, 4 и 6. Например, при будет отправляясь от вычисляем

К моменту входа в -цикл в строке 8 полином всегда будет иметь степень 0, т. е. будет равен постоянной. Например, при будет станет значением для Эта формула для согласуется с определением

Покажем, что алгоритм 7.1 корректен.

Теорема 7.3. Алгоритм 7.1 вычисляет дискретное преобразование Фурье.

Доказательство. В строке а в строке Поэтому с помощью лемм 7.2 и 7.3 легко доказать индукцией по что остаток от деления на Тогда для лемма 7.3 гарантирует, что -цикл в строке 8 присвоит всем правильные значения (остатки, равные постоянным).

Теорема 7.4. Алгоритм 7.1 тратит время

Доказательство. Каждое выполнение строк 6 и 7 занимает О а шагов. При фиксированном цикл в строках 3—7 повторяется раз, занимая в целом время не зависящее от Внешний цикл, начинающийся в строке 2, выполняется раз, занимая в целом время Цикл в строке 8 не требует выполнения арифметических операций.

В теореме 7.4 мы предполагали, что число фиксировано. Поэтому степени элемента , а также значения получаемые из в строках 5 и 8, можно вычислять заранее и использовать как постоянные в неветвящейся программе. Если же надо, чтобы было параметром, можно вычислить степени элемента со и запомнить их в виде таблицы за шагов работы РАМ. Более того, хотя на вычисление в строках 5 и 8 тратится шагов, всего производится не более таких вычислений, так что весь алгоритм при реализации на РАМ имеет временную сложность

Следствие 1. Свертку где векторы размерности можно вычислить за шагов.

Доказательство. В силу теорем 7.1, 7.3 и

Следствие 2. Положительно и отрицательно обернутые свертки векторов можно вычислить за шагов.

Алгоритм 7.1 был изложен для того, чтобы пояснить интуитивные соображения, лежащие в основе его конструкции. На самом деле при вычислении БПФ можно работать лишь с коэффициентами и тем самым упростить алгоритм. Это реализовано в алгоритме 7.2.

Алгоритм 7.2. Упрощенный БПФ-алгоритм

Вход. Вектор где для некоторого целого числа

Выход. Вектор где при

Метод. Применяем программу на рис. 7.4. Для облегчения понимания вводим временный массив чтобы хранить результаты предыдущего шага. На практике эти вычисления можно осуществлять на том же месте.

Когда строка 3 выполняется первый раз, коэффициенты полинома хранятся в массиве Во время первого выполнения строки 6 полином делится на Получаются остатки

(см. скан)

Их коэффициенты хранятся в массиве при втором выполнении строки 3. Коэффициенты первого остатка занимают первую половину массива а второго остатка — вторую половину

При втором выполнении строки 6 каждый из этих двух полиномов-остатков делится на два полинома вида Это дает четыре остатка, каждый степени Их коэффициенты при третьем выполнении строки 3 запоминаются в Строка 7 реорган зует компоненты ответа так, чтобы они шли в правильном порядке. Она нужна потому, что корни из единицы были переставлены, чтобы устранить члены, получающиеся от перекрестных умножений при вычислении произведений полиномов Этот процесс при частично проиллюстрирован на рис. 7.5.