Обратная операция а = DFT"1/) состоит в умножении матрицы V~l (обратной к Vn) на у. Теорема 32.7

Элемент с индексами (j,k) матрицы V~l равен и>п~кз/п. Доказательство

Покажем, что V~1Vn = In, где 1п - это единичная (га X га)-матрица. По определению,элемент произведения V~1Vn

есть

п-1п-1

к=0к=0

Последняя сумма равна 1 при j = j и равна 0 при j ф j по лемме о сложении (лемма 32.6). В самом деле, -(га - 1) j - j п - 1, так что j - j не делится на га при j ф j.

Зная обратную матрицу V~x, мы можем найти а = DFT"1/) по формуле

п - 1

aJ = -J2yk<kj,32.11

к=0

для j = 0,1,... , га - 1. Сравнив формулы (32.8) и (32.11), мы видим, что для вычисления обратного преобразования Фурье можно применить тот же алгоритм (быстрого преобразования Фурье), поменяв в нём any местами, заменив ujn на lo~x и разделив каждый элемент результата на га (см. упр. 32.2-4). Таким образом, DFT"1 также можно вычислить за время ©(гаlgra).

Итак, мы научились переходить от коэффициентов многочлена к набору его значений в корнях из единицы и обратно за время О (га lgra). Это умение можно использовать для умножения многочленов. Сформулируем соответствующий результат в виде теоремы:

Теорема 32.8 (о свёртке)

Для любых векторов а и Ь размерности га, где га - степень двойки выполнено равенство

а ® Ь = 1)1- i,1 (1)1- 1 , (а) • 1)1- i., (6)),

если дополнить векторы а и Ь нулевыми элементами до длины 2га, и через • обозначить покомпонентное произведение двух 2га-элементных векторов.

Упражнения

32.2-1

Докажите следствие 32.4 32.2-2

Найдите дискретное преобразование Фурье вектора (0,1,2,3). 32.2-3

Выполните упр. 32.1-1, используя схему быстрого (время ©(гаlgra)) алгоритма умножения многочленов (рис. 32.1).

32.2-4

Напишите процедуру вычисления DFT"1 за время O(ralgra). 32.2-5

Как быстро выполнить преобразования Фурье, если га является степенью тройки? Напишите рекуррентное соотношение для времени работы соответствующей процедуры и решите его.

32.2-6*

Преобразование Фурье вектора из га элементов можно вычислять не над полем С, а в кольце Zm целых чисел по модулю то, где т = 2fn/2 + 1, где t - произвольное положительное целое число. При этом роль ujn играет 2*. Покажите, что дискретное преобразование Фурье и обратное к нему для векторов с элементами из этого кольца корректно определены и могут быть вычислены за время О (га lgra) по той же схеме.

32.2-7

Покажите как для данного списка чисел zo, z\,... , zn \ (не обязательно различных) найти коэффициенты многочлена Р(х) степени меньше га, имеющего указанные в списке корни (с учётом кратности). Время работы должно быть О (га lgra). (Указание. Многочлен Р(х) обращается в нуль в точке а тогда и только тогда, когда делится на (ж - а).)

32.2-8*

Рассмотрим преобразование вектора а = (ao,cii,... ,ara i), переводящее его в вектор у = (уо, у\,... , yn-i), заданный формулой yk = X}j=o ajzjk, гДе z - произвольное комплексное число. (Дискретное преобразование Фурье является частным случаем для z = ujn.) Докажите, что это преобразование можно выполнить за время О (га lgra) для любого комплексного числа z. (Указание: используйте равенство

п-1

yk = zll2W-{k-1?l\

чтобы представить результат преобразования как свёртку.)

32.3 Эффективные реализации быстрого преобразования Фурье Дискретное преобразование Фурье часто встречается на практике, причём в ситуациях, где скорость работы очень важна (обработка сигналов и т.п.). В этом разделе рассматриваются две эффективные реализации быстрого преобразования Фурье. Сначала мы рассмотрим итеративный алгоритм быстрого преобразования Фурье, который имеет лучшие константы в асимптотической оценке О (га lgra), чем рекурсивный алгоритм раздела 32.2. Затем мы используем те же идеи для быстрой параллельной реализации. Итеративная реализация быстрого преобразования Фурье Прежде всего заметим, что в цикле for в строках 10-13 процедуры Recursive-FFT дважды вычисляется значение и>кпу. Введя

Рис. 31.4 32.3 Преобразование бабочки. Слева поступают два входных знак[1]

чения, ш„ умножается на ук , справа выдаются значения суммы и разности. Рисунок можно рассматривать как схему, составленную из элементов сложения, вычитания и умножения.

Рис. 31.5 32.4 Дерево входных векторов для рекурсивных вызовов процедуры recursive-FFT. Исходным является вызов при п = 8.

временную переменную t, можно запомнить значение этого общего подвыражения (common subexpression - терминология, используемая разработчиками компиляторов), чтобы не вычислять его вторично:

for $k \leftarrow 0$ to $n/2-l$

\quad do $t \leftarrow \omega y k~{[l]}$

\qquad $y k \leftarrow y k~{[0]} + t$

\qquad $y {k+(n/2)> \leftarrow y k~{[0]} - t$

\qquad $\omega \leftarrow \omega \omega n$

Выполняемые в этом цикле действия показаны на рис. 32.3; их называют преобразованием бабочки (butterfly operation).

Сейчас мы покажем, как построить итеративный (а не рекурсивный) вариант быстрого преобразования Фурье. На рисунке 32.4 показаны входные векторы в дереве рекурсивных вызовов процедуры Recursive-FFT, начиная с ее вызова для п = 8.

Указаны входные векторы для рекурсивных вызовов процедуры Recursive-FFT; каждый такой вызов порождает два новых (для векторов половинной длины). На рисунке левый потомок соответствует первому из них, а правый - второму.

Эти рекурсивные вызовы можно заменить вычислением снизу вверх. Расположим элементы исходного вектора а в том порядке, в каком они появляются в листьях дерева (нижняя строка). Затем возьмём пары элементов, вычислим для них дискретное преобразование Фурье, используя преобразование бабочки. Получится содержимое второй снизу строки рисунка. (Элементы исходного вектора больше не нужны, так что можно записать результаты преобразований на их место.) Теперь из каждых двух пар мы собираем четвёрку, дважды выполнив преобразование бабочки, получается га/4 четвёрок. Далее из четвёрок собираются восьмёрки и т.д.; на последнем шаге из двух векторов длины га/2, являющихся преобразованиями Фурье чётной и нечётной части вектора а, изготавливается преобразование Фурье всего вектора а.

Соответствующая программа использует вектор А[0..п- 1] в который в начале работы мы помещаем элементы вектора а в том порядке, в котором идут листья дерева рис. 32.4. (Что это за порядок, мы обсудим дальше.) Введём также переменную s, в которой