32. Многочлены и быстрое преобразование Фурье Стандартные способы сложения и умножения двух многочленов степени п требуют времени О(га) и 0(га2) соответственно. В этой главе описывается, как уменьшить время умножения до ©(га lgra) при помощи быстрого преобразования Фурье (Fast Fourier Transform, FFT). Многочлены

Многочлен (polynomial) А(х) от переменной х над полем F (polynomial in the variable x over F) имеет вид

n-l

E

3=0

Значения ао, ai, ... , an-\ принадлежат полю F (в большинстве наших примеров F будет полем комплексных чисел С). Они называются коэффициентами (coefficients) многочлена. Наибольший из показателей степеней с ненулевыми коэффициентами называется степенью (degree) многочлена. Таким образом, наша формула дает общий вид многочлена степени меньше п (polynomial of degree-bound п).

Пусть А(х) и В(х) - два многочлена степени меньше п. Если мы их сложим, то получим их сумму (sum), многочлен С(ж) степени меньше п, коэффициенты которого есть суммы соответствующих коэффициентов А(х) и В(х). В этом случае С(х) = А(х) А- В(х) для всех х из поля F. Таким образом, если

п-1 3=0

а

п-1

B{x) = YJb]x\

3=0

то

п-1 3=0

где Cj = aj + bj для j = 0,1,..., п - 1. Например, если А(х) = 6ж3 + 7ж2-10ж + 9, а В(ж) = -2ж3 + 4ж-5, тогдаС(ж) = 4ж3 + 7ж2-6ж + 4.

Результатом умножения двух многочленов А(х) и В(х) будет их произведение (product) - многочлен С(ж), для которого С(ж) = А(х)В(х) для всех ж из поля F. Умножение выполняется так: каждое слагаемое многочлена А(х) умножается на каждое слагаемое многочлена В(х), после чего выполняется приведение подобных членов (слагаемых с одинаковыми степенями). Например, мы

можем умножить А(х) = 6ж3 + 7ж2 - 10ж + 9 на В(х) = - 2ж3 + 4ж - 5 следующим образом:

[здесь приводится умножение столбиком - надо взять его из оригинальных файлов]

/„6х~3 + 7х~2 - 10х + 9

/„-2х~3+ 4х - 5

-30х~3 - 35х~2 + 50х - 45 24х~4 +28х~3 - 40х~2 + 36х -12х~6 -14х~5 +20х~4 -18х~3

/„ -12х~6 -14х~5 +44х~4 -20х~3 - 75х~2 + 86х - 45

Другими словами, произведение С(ж) двух многочленов А(х) и В(х) степени меньше га определяется как

2п-2

С{х) = сзх(32-!)

где

j

cj = 2iakb3 k.(32.2)

k=0

Степень многочлена-произведения равна сумма степеней сомножителей:

degree(C) = degree(A) + degree( B).

Поэтому произведение многочленов степеней меньше то и га будет многочленом степени меньше то + га - 1 (и тем более меньше то + га). План главы

В разделе 32.1 рассматриваются две способа представления многочленов: как набор коэффициентов и с помощью набора значений в заданных точках. Выполнение умножения по формуле (32.2) требует времени 0(га2), если многочлены задаются своими коэффициентами. Если многочлены задаются своими значениями в некоторых точках, то для умножения достаточно времени О (га) (умножаем значения поточечно). Используя переход от одного представления к другому и поточечное умножение, мы сможем выполнять умножение (находить коэффициенты произведения по заданным коэффициентам сомножителей) за время в (га lgra). Для этого нам потребуются комплексные корни из единицы, преобразование Фурье и обратное к нему (раздел 32.2). В разделе 32.3 описываются быстрые последовательные и параллельные реализации преобразования Фурье.

Поскольку мы постоянно используем комплексные числа, в этом разделе символ г зарезервирован для мнимой единицы (\/- 1).

32.1 Представление многочленов

Многочлен можно задать, указав его коэффициенты, а можно - набором его значений в некотором числе точек. Переход от одного способа к другому будет использован для умножения двух многочленов степени меньше га за время в (га lgra).

Задание многочлена вектором коэффициентов

Многочлен А(х) = азх3 может быть задан вектором коэффи-

циентов а = (ао, а\,..., ara-i) (coefficient representation). (В матричных уравнениях этого раздела мы будем использовать в основном векторы-столбцы.)

Представление многочлена коэффициентами удобно в целом ряде случаев. Например, операция вычисления значения многочлена А(х) в данной точке xq (evaluating the polynomial at a given point) может быть выполнена за время в (га) по схеме Горнера (Horners rule):

А(хо) = а0 + х0(а1 + х0(а2 Н-----Ь х0(ап 1)) ...)).

Сложение многочленов, заданных векторами коэффициентов, также требует времени в (га): если многочлены заданы векторами коэффициентов а = (ао, а\,..., ara-i) и Ь = (bo, Ь\,..., bn i), то их сумма задается вектором с = (со, с\,..., cn i), в котором Cj = aj + bj для j = 0,1,.. .,га - 1.

Теперь рассмотрим умножение двух многочленов А(х) и В(х), степени ниже га. Если непосредственно использовать формулу 32.2), то на вычисления потребуется время 0(га2), поскольку каждый коэффициент вектора а надо умножить на каждый коэффициент вектора Ь. Поэтому важно научиться экономить при умножении - самой трудоемкой из рассмотренных операций. Другими словами, мы хотим быстро вычислять вектор с, заданный уравнением (32.2). Он называется свёрткой (convolution) векторов а и Ь и обозначается с = а (?) Ъ. Вычисление свёртки (иными словами, умножение многочленов, заданных векторами коэффициентов) часто встречается на практике.

Задание многочлена набором значений

Фиксируем га различных точек хо, х\,... , хп-\. Многочлен А(х) степени ниже га однозначно определяется своими значениями в этих точках, то есть набором из га пар аргумент-значение

для к = 0,1,..., га - 1. Таким образом, для каждого набора точек хо, х\,..., xn i мы получаем свой способ представления многочленов с помощью значений в этих точках.

п-1

{(х0,уо), (xi,yi),..., (a;n i,yn i)}

где

(32.3)