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

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

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

Затем докажем теорему о свертке. Свертку будем интерпретировать как вычисление полиномов в корнях из единицы, умножение этих значений и последующую интерполяцию полиномов. С помощью быстрого преобразования Фурье разработаем эффективный алгоритм для свертки и применим его к формальному (символьному) умножению полиномов и умножению целых чисел. Получающийся алгоритм умножения целых чисел, называемый алгоритмом Шенхаге — Штрассена, является асимптотически самым быстрым из известных способов умножения двух целых чисел.

7.1. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ОБРАТНОЕ К НЕМУ

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

коммутативным кольцом Элемент из обладающий свойствами

называется примитивным корнем степени из единицы. Элементы называются корнями степени из единицы.

Например, где является примитивным корнем степени из единицы в кольце комплексных чисел.

Пусть будет -мерным вектором -столбцом) с элементами из Мы предполагаем, что элемент обладает в этом кольце обратным относительно умножения 2) и что — примитивный корень степени из единицы в этом кольце. Пусть А — такая -матрица, что Дискретным преобразованием Фурье вектора а называется вектор обозначаемый также ; его компонента равна Матрица А невырожденна, и, значит, существует обратная к ней матрица ее простой вид описывается в лемме 7.1.

Лемма 7.1. Пусть коммутативное кольцо, — примитивный корень степени из единицы и как элемент кольца имеет обратный. Пусть -такая -матрица, что Тогда существует матрица и элемент ее равен

Доказательство. Пусть если в противном случае. Достаточно показать, что если матрица определена, как выше, то т. е. элемент матрицы удовлетворяет равенству

Если то левая часть равенства (7.1) превращается в

Пусть и Тогда левая часть в (7.1) равна

Если

поскольку — примитивный корень степени из единицы. Если то, умножив левую часть на изменив порядок слагаемых и подставив вместо получим

Эта сумма тоже равна 0, поскольку примитивный корень степени из единицы. Отсюда сразу вытекает (7.1).

Обратным дискретным преобразованием Фурье вектора а называется вектор компонента которого, равна

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

Преобразование Фурье тесно связано с вычислением полиномов и их интерполяцией. Пусть

— полином степени. Его можно однозначно представить двумя способами: списком его коэффициентов и списком его значений в различных точках Процесс нахождения коэффициентов полинома по его значениям в точках называется интерполяцией.

Вычисление преобразования Фурье вектора эквивалентно превращению представления полинома списком его коэффициентов в представление его списком значений в точках Точно так же вычисление обратного преобразования Фурье эквивалентно интерполяции полинома по его значениям в корнях степени из единицы.

Можно было бы определить преобразование, которое вычисляло бы значения полинома на множестве точек, отличных от корней из единицы. Например, можно было бы использовать целые числа Однако мы увидим, что, выбирая степени корня со, мы делаем вычисление значений и интерполяцию особенно простыми. В гл. 8 преобразование Фурье применяется для вычисления значений и интерполяции полиномов в произвольных точках.

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

два вектора-столбца. Их сверткой называется такой вектор что (Полагаем если или Таким образом,

Заметим, что эта компонента включена только для симметрии.

Чтобы мотивировать рассмотрение свертки, снова обратимся к представлению полинома его коэффициентами. Произведение двух полиномов степени

является полиномом степени

Заметим, что коэффициенты произведения — это в точности компоненты свертки векторов составленных из коэффициентов исходных полиномов (коэффициентом равным 0, мы пренебрегаем).

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

преобразование. Единственная трудность состоит в том, что произведение двух полиномов степени вообще говоря, является полиномом степени и для его представления требуются его значения в различных точках. В теореме 7.1 показывается, как преодолеть эту трудность. Можно рассматривать как полиномы степени которых равны нулю коэффициенты при старших степенях полиномы степени считать полиномами степени

Теорема 7.1. (Теорема о свертке.) Пусть

и

— векторы-столбцы размерности а

и

— их преобразования Фурье. Тогда

Доказательство. Так как для то при

Следовательно,

Пусть Так как то

Меняя порядок суммирования в (7.3) и подставляя вместо получаем

Так как для можно повысить нижний предел суммирования во внутренней сумме до Аналогично, поскольку для можно понизить верхний предел во внешней сумме до Верхний предел внутреннего суммирования не меньше

независимо от значения Таким образом, можно заменить верхний предел на так как при После этих изменений (7.4) превратится в (7.2); отсюда следует, что Итак, откуда

Свертка двух -мерных векторов является -мерным вектором. Это требует, чтобы в теореме о свертке вектора были "разбавлены" нулями. Чтобы избежать этого "разбавления", введем понятие обернутой свертки.

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

Отрицательно обернутой сверткой векторов называется такой вектор что

В разд. 7.5 мы воспользуемся обернутой сверткой в алгоритме Шёнхаге — Штрассена — алгоритме быстрого умножения целых чисел. А пока отметим следующее. Вычислив значения двух полиномов степени в корнях степени из единицы и перемножив пары значений в соответствующих точках, мы получим значений, по которым сможем однозначно интерполировать полином степени Вектор коэффициентов этого единственного полинома как раз и будет положительно обернутой сверткой векторов коэффициентов исходных полиномов.

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

1) положительно обернутая свертка векторов равна

2) если отрицательно обернутая свертка векторов

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