матрицы постсложений множители 1/2. Таким образом,

1 ol

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

Наконец, матрица постсложений имеет вид

1 -1

Описанный алгоритм в матричной форме приведен на рис. 3.9. Порядок выполнения сложений в такой форме алгоритма не ука-зан. Читатель может сам поэкспериментировать с выбором по- i рядка сложений, минимизируя их число; никакой специальной теории выполнения такой минимизации не разработано. Легко выполнить все предсложения с помощью четырех вещественных сложений. Постсложения можно реализовать с помощью следующих восьми вещественных сложений:

So = S , % = + Cl + Sj,

Cl = Sl - Sj, Sl = Sl + Cj - S2,

Ca = Sj -f Sj, S3 = C3 - So -f Sl.

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

10 0 0 0 1 1 2 1-1 1 0-2 О 2 I I 0-1 -1

i О

. 1 1

10 0

I 1 1

1 1-1

1 0-1

о 1 о

Рис. 3.9. Пример алгоритма Винограда вычисления свертки.

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

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

s{x) = Q(x)m(x) + [s(x)].

Мы уже рассмотрели случай deg т (х) > deg s (х), в котором частное Q (х) тождественно равно нулю. Если deg т (х) < deg s (х), то алгоритм Винограда позволяет вычислить s (х) по модулю многочлена т (х). Член Q (х) ш (х) представляет собой погрешность, которую можно вычислить дополнительно и прибавить к результату. Простейшим является случай, когда deg т (х) = = degs(x). Тогда многочлен Q (х) является константой, так как его степень должна быть равной нулю. Если т (х) - приведенный многочлен степени п, то, очевидно, Q (х) = s , где s - коэффициент при х в многочлене s (х). Следовательно,

S (х) = s /n (х) + R ( Is (х) 1,

и s легко вычисляется как произведение старших коэффициентов многочленов g {х) и d (х).

Эту модификацию можно формально включить в основной алгоритм Винограда для вычисления свертки путем замены многочлена т (х) формальным выражением т (х) (х - оо). Утверждение

S (х) = S (х) (mod т (х) (х - оо))

представляет собой просто удобное сокращение для данного выше точного утверждения.

Вернемся к предыдущему примеру и применим описанную модификацию алгоритма к вычислению свертки

S (X) = (gix -f go) (djx 4- dix -Ь do). В качестве модуля выберем теперь многочлен х (х - 1) {х + -Ь 1) (х - оо). Алгоритм будет содержать четыре умножения;

4 Блейхут Р.

множителю {х - оо) соответствует произведение gid, а остальные три умножения - это произведения вычетов по модулям х, х - 1 и X -\- [. Сразу видно, что

Коэффициенты многочлена s (x) вычисляются в соответствии с китайской теоремой об остатках:

S (X) = а< ) (X) S + aW (х) S, + а<> (х) S, + х (х - 1) (х + 1) S3 =

= (-х + 1)So+ (4-х + 4- х) S, + (т - Т ) 5 + Следовательно,

Окончательная формулировка алгоритма приведена на рис. 3.10. Алгоритм содержит четыре умножения и семь сложений при условии, что диагональная матрица вычисляется заранее.

Рнс. 3.10. Другой пример алгоритма Винограда вычисления свертки.

3.4. Построение алгоритмов

коротких линейных сверток

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

Иногда хорошие алгоритмы удается получить с помощью удачной факторизации. Рассмотрим следующие тождества:

g di + g,d = (go + gi) (d + d,) - g do - gjdi, g (4 + gA + еЛ = (go + Si) (do + (4) - goo +

+ ёЛ-еЛ.

еЛ + = (gi + gj) (dl + da) - gidi - gjd gA = gA-

Этл тождества позволяют вычислить коэффициенты свертки s (х) = = (go + g: + gj- *) (do + di + daX-) с помощью шести умножений и десяти сложений. Этот алгоритм, однако, не может быть построен с помощью китайской теоремы об остатках. Матричная форма записи алгоритма дается равенством

1 0 0 0 0 0 8, 1-1 О I 0 0 - I 1-1 о

о - 1 -1

о о I

1 о о о 1

<go + S,)

(е. + Si)

(Sl + 1

1 О о

о I о

0 о 1

1 I о I о I О 1 I

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

На рис. 3.11 затабулированы характеристики некоторых алгоритмов линейных сверток; на рис. 3.12 приведены некоторые нз них.

Оптимальный алгоритм линейной (ЗХЗ)-сЕертки выписан в виде примера на рис. 3.12. Ойтима.чьный по числу умножений алгоритм содержит пять умножений. Он подсказан описанным в разд. 3.8 алгоритмом Кука - Тоома, который также содержит пять умножений. По существу он совпадает с алгоритмом Кука - Тоома и получается выбором многочлена

m (х) = X (X - 1) (X -f 1) (х - 2) (X - оо).

Так как все множители являются многочленами первой степени, то всего имеется пять умножений. (Если заменить один из множи-4

S (х) = g (*) d (х) degg(x)= L-\ deg d{x) = N -\

Вещественные свертки

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

Линейная свертна 2*Ъ 3 умножеммя, 3 сложения

10 0 -I 1-1 О О I

П о1

Линейная свертна 3x3 Ъ умомеммй, 20 сложений

О О ~1 -1 3 О

01 Ti

Предсложения

(j = rfj - rf,

Z) = + r, = rfo + h D) =/, + /, + (3 + D,

1 + 2)

iigb + 2gi

Постсложения

io = 5o + So

Г, = S + s,

7-; = 5г + Sj

Г, = * S4

Г. = r, - So - S,

T, = 5, +

J, = Г - r, *

Sj = -So + -t- Г, - S4

I, = - Г4 - r,

5. =

Рис. 3.12. Некоторые алгоритмы вычисления линейных сверток.

телей многочленом второй степени, то получим шесть умножений, но меньшее число сложений.) Выходной многочлен дается равенством S {X) = (.+,> (.-2) [g {X) d {х)\ + g2d2X (X - 1) (X + 1) (л- - 2). Остатки определяются матричными уравнениями

где с целью сохранения стройности и упорядоченности принятых обозначений G, и D, формально определяются как вычеты по модулю многочлена (х - оо). Таким образом, 5(, = GJ~)k Для = О, 4. Наконец, используя китайскую теорему об остатках, для многочлена s (х) получаем выражение

s(x) = -i-S (x -2x=-x-

+ 4-5Л- + Зх-2х)-Запись последнего шага

-2)--i-S,(x -x -2x) +

~-1 S3 (х- X) + S* (х* - 2х + х + 2х). в матричном виде дается равенством

Постоянные множители можно похоронить в константах диагональной матрицы, переопределяя величины и 0. Для выполнения свертки требуется пять умножений. Матрица предсложений может быть реализована семью сложениями, а матрица постсложений 13 сложениями.

Окончательная форма алгоритма показана на рис. 3.12. Хотя алгоритм построен для поля вещественных чисел, он пригоден и в поле комплексных чисел: пять умножений становятся пятью комплексными умножениями, а 20 сложений становятся 20-ю комплексными сложениями.