рис. 7.5. Характеристики усиленного алгоритма Агарвала-Кули вычисления свертки.

зуя для свертки многочленов произведения по модулю у - 1, а длГчисения s< (х, у) - гнездовой алгоритм, основанный насГертке мТогочлено;по1одулю X - 1, вложив в не умножение многочленов по модулю у* + у + у + у + Наконец, произведение s (х, у) вычислим по правилу

(X, !/)-fa (r/)s (. у) (mod/ - l).

six. у) = а (у)/ , , , . . где й ) (у) и дС) (у) вычисляются в соответствии с китайской теоремой об остатках для многочленов. Они равны тем же многочленам, которые должны использоваться для s° ({/) и s (у) в одномерной задаче вычисления произведения многочленов по мо. дулю / - 1.

Как мы видим, вычисление разбито на те же подзадачи, что рассматривались и ранее, но сочетаются они несколько иначе. Теперь мы пользуемся китайской теоремой об остатках после выполнения гнездового алгоритма, перед которым была проведена одна редукция многочленов. Чтобы подсчитать число необходимых сложений, остановимся подробнее на числе сложений, необходимом для выполнения 5-точечной циклической свертки. Оно равно:

умножение многочленов по модулю у - i- О сложений, умножение многочленов по модулю

У* + г/ + -)- У + 1: 16 сложений,

китайская теорема об остатках: 15 сложений.

s -°(. y) = g - (x. j,)d °4x, у) (mod(mod? ({/)), (х, s) = (. J/)d (x, ;/) (mod/ (x))(mod? (i,)),

g -4x. y) = g(x. y) (mod p (x)) (mod? (</))

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

Пусть Мо и Ml обозначают число умножений, необходимых для вычисления произведения многочленов по модулю р (х) и р (х) соответственно, а Мо и Afi - число умножений, необходимых для вычисления произведения многочленов по модулю qf°> (у) и {у) соответственно. Тогда прямой метод вычисления произведения

S {X, 1/) = г (х, у) d (х, у] (mod р (х)) (mod q {у))

требует М = {Мо + М,) {Ml, -f М,) умножений, а описанное использование китайской теоремы об остатках на двумерных фрагментах М = МоМо + МоМ, + MiMo + MiMt умножений, так что число умножений не уменьшается.

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

Имеется много способов разбиения задачи вычисления двумерной свертки с помощью китайской теоремы об остатках. На рис. 7.5 приведены примеры характеристик, которые могут быть получены путем модификации алгоритма Агарвала-Кули с помощью описанных разбиений. Данные на рис. 7.5 следует сравнить с приведенными на рис. 7.4 характеристиками.

В качестве примера опишем построение алгоритма 20-точечной циклической свертки. Сначала преобразуем свертку в двумерную (4x5)-свертку

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

Разложим теперь этот алгоритм на двумерные фрагменты в виде

i/) = g<°(x, i()d<°(,.</) (modx-l) (mody-1),

s-\x, y)i\x, y)d\x, у) (modx*-l) {mods*+i/ +

Дальнейшего разложения на двумерные фрагменты делать не будем, а применим к вычислению s* (х, у) гнездовой алгоритм вычисления произведения многочленов по модулю х* - 1, исполь-

Вычисления по модулю л;* - 1 содержат 15 сложений. Таким образом, перебирая все три составляющие, для полного числа сложений в рассматриваемом двумерном алгоритме получаем А (20) = (4 0 + Ы5) + (415 + 516) + (15.4) = 215,

что меньше, чем 230 сложений, необходимых в чистом алгоритме Агарвала-Кули.

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

Чтобы на основании китайской теоремы об остатках добиться дальнейшего уменьшения числа умножений, надо ввести еще одну идею; надо подняться в такое расширение поля, в котором задача начнет распадаться. Можно допустить разложение многочлена q (у) на взаимно простые множители, коэффициенты которых зависят от неопределенной переменной х. (Говоря формально, можно рассмотреть разложение многочлена q {у) в расширении поля, получаемом присоединением формальной переменной х.) Это приведет к тому, что многочлен q {у) может распасться на множители, степени которых меньше возникавших ранее в одномерных задачах степеней. Следовательно, могут быть построены алгоритмы с лучшими характеристикам]}. При этом символ х появится в свертке по у, так что сама по себе свертка по у становится более сложной. Но при переходе в алгоритм свертки по х возникающий при разложении q {у) символ х может алгебраически взаимодействовать с символом X в свертке по х, что упрощает двумерный алгоритм.

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

S (х, у) = g (х, у) d (X, у) (raodx -1) (mody -I).

Разобьем задачу на две подзадачи:

s< i (X, у) = gi ! (X, у) d i (X, у) (mod у* - I) (mod х - I)

s 4x, y)=g (x, y)d {x, у) {mody~ l) (modx-- l). Решение первой подзадачи уже рассматривалось; алгоритм вычисления этой свертки содержит десять умножений, если его строить иа основании 4-точечного и 2-точечного алгоритмов циклических сверток, содержащих 5 и 2 умножения соответственно.

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

I/* - 1 и по модулю х + 1 соответственно, требующими 15 умножений, то получим в результате алгоритм, содержащий 25 умножений, - тот же результат, который получится, если использовать по обоим измерениям алгоритм 4-точечной циклической свертки.

Вместо этого рассмотрим разложение

J/ - 1 = (г/ - I) (У + 1) (У -х){у + X) (mod х + 1). Такая запись осмысленна, поскольку по модулю х + I выполняется равенство х? = -1. Теперь можно построить алгоритм вычисления по модулю у ~ I с четырьмя умножениями. Каждое из умножений представляет собой умножение многочленов от х первой степени по модулю х + 1. Но умножения многочленов первой степени в любом случае входят в алгоритм. Используя разложение у + I = (у - х) (у + х), мы как бы частично уменьшаем зависимость по у, перенося ее в зависимость по х и перекладывая часть работы в вычисления по х, которые приходится выполнять в любом случае.

Этот путь позволяет вычислить s<4 (х, у) за 12 умножений, так что исходный алгоритм циклической (4 X 4)-свертки будет содержать 22 умножения-

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

7.4. Итеративные алгоритмы

Итеративные методы построения алгоритмов свертки бази-руются на том, что малые алгоритмы свертки, независимо от того, в каком именно поле F они были построены, на самом деле представляют собой некоторые тождества, справедливые в любом со. держащем поле F кольце. Окончательный алгоритм не предполагает коммутативности умножения и не содержит делений, за исключением деления на некоторые малые константы. В качестве операций над входными переменными допускаются только сложения, вычитания и умножения.

Сначала рассмотрим линейную одномерную 4-точечную свертку S (х) = g (х) d (х), где степень многочленов g (х) и d (х) равна трем. Расставим скобки по правилу:

8 {X) = (gaX + gj х= + (g,x + go).

d (X) = (daX + d,) x + (diX + d ).

Определим следующие многочлены от двух переменных: g (у. г) = {giy -г gi) г + {giu + go). d (у, z) = (d,y + 4) г + (dy + d ), {y< г) =g{y,z)d (y, г).

Тогда искомая свертка получается из многочлена s (у, г) по пра. вилу

S (X) = S (X, х).

В сокращенной форме эти вычисления могут быть записаны равенством

+ Z + s (</) =igi{y) г + g,{y]) (dM z +

в котором все коэффициенты представляют собой многочлены от у первой степени.

Алгоритм 2-точечной линейной свертки записывается в виде

[о о

Эти тождества справедливы даже тогда, когда входные переменные являются элементами кольца многочленов. Соответственно

0 о1

1 -1

П 0] им

Здесь имеются три умножения многочленов и три сложения многочленов, исключая сложения, относящиеся к коэффициентам многочлена g (х). Каждое произведение многочленов само является 2-точечной линейной сверткой и, следовательно, требует три умножения и три сложения. Таким образом, полное число умножений в итеративном алгоритме 4-точечной линейной свертки равно 9, тогда как оптимальный алгоритм содержит только семь умножений. Преимущество итеративного алгоритма состоит в уменьшении числа сложений: исключая сложения, касающиеся коэффициентов многочлена g (х), он содержит всего 15 сложений.

Полученный алгоритм 4-точечной свертки можно итерировать опять и построить алгоритм 16-точечной свертки, содержащий 81 умножение и 195 сложений (5.06 умножений и 12.19 сложений на одну компоненту на выходе). Этот алгоритм можно в свою очередь итерировать опять для построения 256-точечной свертки алгоритма с 6561 умножениями и 18 915 сложениями (25.63 умножений и 73.89 сложений на одну компоненту на выходе).

В общем случае для вычисления s (х) = g (х) d (х) можно использовать итерацию, если число коэффициентов многочлена g (х) и число коэффициентов многочлена d (х) имеют общий делитель. Пусти deg d (х) ~- MN - 1 и deg g (х) ~ ML - 1. Преобразуем многочлен d (х) в многочлен от двух переменных d (у. г), полагая н-\ /.м-1 \

* d{y. г)= {l,dM,k/]z,

где старый индекс ( связан с парой (к, I) новых индексов равенством i = М1 + к, ; = О, л- - 1, * = о, М - 1. Аналогично, многочлен g (х) также преобразуем в многочлен от двух переменных g (у, г), полагая

g{y. г) = s( eaWI.

где / Ml i-k, I = О, I - 1 и ft = 0. .... Ж - I. Вы-числи.м произведение s {у, г) g {у, г) d {у, г). Тогда s (х) можно вычислить согласно равенству

S (х) - S (X, х),

для чего требуются только сложения. Этот двумерный алгоритм свертки основан на алгоритме линейной свертки последовательностей длины L \\ N я алгоритме М-точечной линейной свертки. 4hCj)io необходимых умножений равно произведению чисел необходимых умножений в двух составляющих малых алгоритмах линейных сверток.

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

Итерацию можно использовать и для вычисления произведения

s{x) = g {х) d (а) (mod т [х)). Простейший способ состоит в вычислении линейной свертки с последующим приведением по модулю многочлена m (х). Но обычно удается добиться лучшего, если усложнить процедуру.

Мы рассмотрим только случай, когда т (х) равно х + 1, причем п представляет собой некоторую степень двойки. Это важный случай, так как

Х2а~- 1 =(Х ~ 1){Х -h 1),

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