7.8. Быстрая свертка многочленов

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

Достаточно рассмотреть двумерную циклическую свертку. Запишем эту свертку в виде одномерной циклической свертки многочленов:

Sf (у) = Е gfif-k-)) {у) df (у) (mod у - 1).

Так как многочлен у - 1 распадается в произведение круговых многочленов, то эту задачу можно разбить на множество подзадач вида

sr (у) = Е gw-t)) iy) dk (у) (mod р (у)).

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

Рассмотрим элементы gi- (у) и di- (у) для всех i = О, п - I как элементы поля Q {(о). Тогда для спектров соответственно имеем для всех к = О, п - 1:

(У) = Е (У) (mod р (у)),

Dk(y) = S У-(У) (niodp((/))

(у) = Gj. (у) Oj. (у) (mod р (у)}. к=0.....п- \.

Используя обратное преобразование Фурье, получаем

Преобразования Фурье не содержат вещественных умножений.

Все умножения в описанной процедуре сосредоточены в спектральных произведениях Gf (у) Df (у). Всего имеется п таких произведений многочленов по модулю р (у), каждое из которых содержит по меньшей мере 2т - 1 умножений. Таким образом, в общей сложности для вычисления двумерной свертки, содержащей пт чисел, требуется п {2т - 1) умножений. На самом деле число умножений, необходимых для вычисления произведения, многочленов по модулю р {у), существенно больше, чем 2т - 1, ио все же достаточно мало для того, чтобы приводить к эффективным алгоритмам. Некоторые подходящие для этой цели алгоритмы приведены на рис. 7.7.

Рассмотрим теперь двумерную циклическую свертку, записанную в виде произведения многочленов:

S (х, у) = g (х, у) d (х, у) (mod х - 1) (mod у - 1). Используя китайскую теорему об остатках, разобьем эту задачу на подзадачи. Детально остановимся только на частном случае, когда п и п равны степеням двойки (и могут совпадать). Метод вычисления является рекуррентным, основанным на использовании двумерных циклических сверток меньшего размера. Таким образом, с помощью рекурсии двумерная циклическая свертка по основанию 2 сводится к некоторому числу меньших подзадач. Пусть п = 2 и п = 2 при т т. Тогда имеет место

разложение

Г -1 = ( -fl )(;/ =-!) =

= ((/-2-fl)...(y V2 l I)(y..V! 1).

Вообще говоря, последний член можно разлагать и дальше, но мы здесь остановимся. Обозначим члены разложения в правой

Доказательство. Используя обратное полиномиальное преобразование, имеем

Si W = 2 gi-, w w=4- 2 2w d> w =

;=.o - /=0 fe=o

n-l /1-1

k=0 (-0

где jt * следует положить равным единице, потому что, как и ранее, все вычисления производятся по модулю х - I. Следовательно,

Si (X) = -i-- (X) (X),

и Gj (х) Ds (х) должны быть равным Sj (х). □

S (X, г/) = S (у) sO (X,

(mod х - 1),

где а<1 {у) при г = О, R - 1 определяются этой же теоремой. Вычисления на этом последнем шаге не содержат вещественных умножений.

Основная часть вычислений падает на вычисление остатков s> (х, у). Эти вычисления разбиваются на два типа, а именно,

s<> (х, у) = gc- (х, у) d> (х, у) (mod х - 1) (mod ((/ + 1))

s> (х, у) = g(> (X, !/) (X, у) (mod х - 1) (mod у - 1).

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

Опуская индекс г, первый тип вычислений запишем в виде задачи

S {х, у) = g (х, у) d {х, у) (mod х - 1) (mod </ + 1),

где т > п12. Эту задачу можно рассматривать как задачу вычисления одномерной свертки в поле Q , а именно,

S (х) = g (х) d (х) (mod х - 1),

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

В частотной области свертка преобразуется к произведениям

вхоа

в алгоритм циклической свертки пт п = 2 , п = 2 , т > т

Вычисление остатков

(/ Кх. У) = <Цх, у) (mod у - 1) d >(x, у) = <Цг. У) (mod Му))

d {y,x)

Свертки ло модулю \ х + 1

s Hy,x-)

Вызвать алгоритм циклической сверщки fx л

Заранее вычисленные значения

Рис. 7.S. Алгоритм многомерной циклической свертки.

Для их вычисления нужно п умножений в Q, каждое из которых представляет собой произведение многочленов по модулю + 1 и поэтому требует 2т - 1 вещественных умножений. Следовательно, для вычисления

S {х, у) =g (X, у) d (х, у) (mod х - 1) (mod У + 1)

части соответственно через /н-i (у)> /о (У) н для г = О, R - 1 определим

d-> (X, y) = d (х. у) (mod /, (</)),

gf) (х, !/) = g {х, у) (mod (!/))

sci (х, !/) = S (X, у) (mod (у)).

Тогда

sM = gr (х, у) d (х, у) (mod х - I) (mod (у)),

и, согласно китайской теореме об остатках для многочленов,

Рис. 7.9. Характеристики некоторых алгоритмов вычисления двумерной циклической свертки.

необходимо всего п {2т - 1) вещественных умножений, а для вычисления исходной двумерной циклической свертки требуется сделать несколько так-их вычислений.

Например, для вычисления двумерной циклической (64x64)-свертки требуется 64-(63) вещественных умножений и вычисления двумерной циклической (64х32)-свертки. В свою очередь, для вычисления двумерной циклической (64х32)-свертки требуется в идеале 32-(63) + 32-(31) вещественных умножений и вычисления одной двумерной циклической (16х32)-свертки. В свою очередь, вычисление двумерной циклической (32х 16)-свертки требует 16-(31) -\г 16-(15) умножений и свертки еще меньшего размера. Продолжая этот процесс до тех пор, пока не дойдем до тривиальной свертки, получаем около 800 умножений. Это существенно меньше, чем число умножений, необходимое при использовании двумерного алгоритма Кули-Тьюки и теоремы о свертке, равное 73 728.

Практические алгоритмы вычисления произведений многочленов, как видно из затабулированных на рис. 7.7 данных, содержат большее число умножений, чем равный п {2т - 1) теоретический минимум, в частности, рассмотренный алгоритм вычисления двумерной циклической (64х64)-свертки содержит на самом деле 17 770 вещественных умножений. Характеристики некоторых других практических алгоритмов вычисления двумерной циклической свертки, построенных по описанному методу, приведены на рис. 7.9.

Задачи

а. Вычислить характеристики алгоритма 7560-точечнон циклической свертки, построенного на основе алгор>1тма Агарвала - Кули.

б. Вычислить характеристики гнездового алгоритма двумерной (504 X

X 504)-СБ5рТК!1.

Алгоритм вычисления 12-точечной циклической свертки можно построить прямо по методу Винограда или по алгоритму Агарвала - Кули, сочетая алгоритм 3-точечной циклической свертки с алгоритмом 4-точечной циклической свертки. Сравнить числа умножений, необходимых в каждом из этих методов.

а. Описать метод построения алгоритма вычисления 6-точечной циклической свертки s{x) = g (х) d {х) (mod х - 1). Сколько необходимо умножений?

б. Воспользуйтесь алгоритмом Агарвала - Кули построения 6-точечной циклической свертки из алгоритма 2-точечной циклической свертки и алгоритма 3-точечной циклической свертки. Сколько необходимо умножений? Воспользовавшись алгоритмом Агарвала - Кулн, привести матрицы алгоритма 15-точечной циклической свертки к стандартному виду

S - CGAd.

Пусть длина циклической свертки равна п = пппп, где все делители взаимно просты. Различные алгоритмы вычисления циклической свертки такой длины получаются различными способами сочетания алгоритмов циклических сверток длин nj, п, Пз и п. Две возможные схемы построения алгоритмов даются следующими правилами расстановки скобок: п = = {( 1Пг) ( а *)} и л - (rti (нз (пв Ы)))-Доказать, что если в каждом паро-сочетанин используемые алгоритмы оптимальны, то обе схемы содержат одинаковое число умножений и сложений,

Алгоритм вычисления комплексной свертки по модулю х -1 описан в разд. 3.7.

а. Построить этот алгоритм как алгоритм двумерного произведения многочленов по модулям л: -4- 1 и / + 1.

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

s{x.y) gix,y)d{x,y) (modx+l) (mody-4l)

или от

S (X. у) g {X, у) d [х, у)

Какой из алгоритмов лучше? . Кольцо кватернионов было определено в задаче 2.15.

а. Записать двумерную циклическую (2Х 2)-свертку

S (X, у)= g (х. у) d (X, у) (mod х - 1) (mod - 1) в виде произведения (4Х4)-матрицы на вектор, содержащий 4 компоненты. Дать алгоритм, содержащий четыре умножения.

б. Записать полиномиальное произведение

S, {х. у) = g {х, у) d {х, у) (mod х + 1) (mod у - 1) в виде произведения (4Х4)-матрицы иа вектор, содержащий 4 компоненты. Дать алгоритм, содержащий шесть умножений.

в. Записать полиномиальное произведение

S (X, у) g [х, у) d (X, у) (mod + 1) (mod у 1) в виде произведения (4Х4)-матрнцы на вектор, содержащий 4 компоненты. Дать алгоритм, содержащий шесть умножений.

9 Блейхут Р.

(modyH 1) (mod;c4 О-