записать в виде (и - 1){и +1), затем применить правило (59) и снова использовать (59) по модулю (и - 1) = (и - 1)(и + 1). Однако легче обобщить китайскую теорему об остатках (59) непосредственно для нескольких взаимно простых множителей. Например,

х{и)у{и) mod91 (и)92(и)93(w)

= {ai{u)q2{u)qsiu){х{и)у{и) modqi{u)) + a2(u)9i(u)93(u)(x(u)y(u) mod 92(11)) + a3(u)9i(u)92(u)(x(u)y(u) mod93(u))) mod 91 (14)92()93(и), (64)

где ai(u)92(u)93(u) + a2(u)9i(u)93(u)+a3(u)9i(u)92(u) = 1. (Это соотношение можно также истолковать другим способом, заметив, что представление в виде частичных отношений 1/91 (и)92(и)9з(и) равно ai(u)/9i(u) + a2(u)/92(u) + аз(и)/9з(и).) Из (64) получим

x(u)y(u)mod(u4-l)=(i(u4u4u+l)x(l)y(l)-i(u3-u4u-l)x(-l)y(-l)

- (u2-1){х{и)у{и) mod (u41))) mod (u-1). (65)

Остается вычислить x{u)y{u) mod (u + 1) и обратиться к правилу (60). Сначала преобразуем х{и) и у{и) mod (u + 1) и получим Х{и) = {xo-X2)+{xi -хз)и, Y{u) = (2/0-2/2) + (2/1 -2/3)w- Затем по правилу (60) вычислим Х{и)¥{и) = Zo + Ziu + Z2u и, преобразовав его по модулю {и +1), получим (Zo - Z2) + Ziu. Вычислить X{u)Y{u) несложно: можно воспользоваться правилом (58) с р{и) = и{и + 1) и получить

Zo = X0Y0, Z, = X0Y0 - iXo-Xi){Yo-Yi) + Х1Г1, Z2 = Х1Г1.

(Тем самым мы заново открыли трюк 4.3.3-(2) более систематическим способом.) Объединив все вместе, получим следующую реализацию {А, В, С) степени 4 циклической свертки:

"4-

(66)

Л110 1\ /1110 1\ /1 1 2 2 0\

11011 11011 11222

iiioil liiioil 112?0/

VllOil/ \liOil/ 1 1 2 2 2/

Здесь 1 обозначает -1 и 2 обозначает -2.

Тензор для циклической свертки степени п удовлетворяет равенству

tij,k = tk,~j,ii (67)

нижние индексы рассматриваются по модулю п, поскольку tijk = 1 тогда и только тогда, когда i + j = к по модулю п, поэтому, если (ац), (bji), (cki)-реализация циклической свертки, т. е. (cki), {b-j,i), (ац); в частности, можно представить (63), преобразовав (66) в

/1 1 2 2 0\ 112 2 2 112 2 0,

4 1 2 2 2/

(68)

/1 1 1 О 1\ /1 1 1 О 1\

110 11 110 11

1 1 1 о 1 I I 1 1 1 о 1

4 10 11/ \iioii/

Сейчас все сложные скалярные величины оказа)Шсь в матрице А. Это важно для практических целей, так как часто необходимо вычислить свертку для нескольких значений 2/0, 2/1, 2/2, Уз, но с фиксированным набором хо, xi, Х2, Х3. В такой

ситуации арифметика для Xj может быть произведена для всех значений сразу и нет необходимости ее пересчитывать. Таким образом, (68) приводит к следующей схеме вычисления циклической свертки wq, wi, w2, wz, где xq, xi, x2, x заранее известны:

«1=2/0+2/2, «2=2/1+2/3, «3 = «1 + «2, «4=«1-«2,

«5=2/0-2/2, «6=2/3-2/1, «7 = «5-«б;

mi = i(Xo +х1+х2+ Хз) • S3, 7П2 = \{Xq -х1 + х2- Хз) Si,

тз = (xo + Xi-Х2-Хз)-Ss, 7П4 = (-хо+xi+Х2-хз)-se, 7П5 = (хз -xi) • 57; ti=mi+7n2, Ь2=тз-[-тъ, h = mi - т2, ti = m - ть;

Wo = tl+t2, Wi=i3 + i4, W2=ti~t2, W3=t3-ti. (69)

Здесь 5 операций умножения и 15 - сложения, хотя определение циклической свертки включает в себя 16 умножений и 12 сложений. Позже будет доказано, что необходимо 5 операций умножения.

Возвратимся к нашей первоначальной проблеме умножения в (54). Воспользовавшись (62), получим реализацию

/4 О 1 1 2 2 0\

0 0 112 2 2 Vo 4 1 1 2 2 О/

/1 О 1 1 1 О 1\ 0 0 110 11

о о 11 i о I Vo 11 i о 1 i/

/1 о о о о о о\ о 1 1 1 о 1 1 0 0 1110 1

0 о 1 i о 11

1 о 1 1 1 о 1 \о 1 о о о о о/

(70)

В этой схеме используется на одну цепочку больше, чем минимальное число умножений в цепочке, но требуется намного меньше операций умножения параметров, чем (57). Конечно, это допустимо, так как схема все ещё достаточно сложна: если нашей целью является простое вычисление коэффициентов zq, zi, ..., Zb произведения двух заданных полиномов (хо + xiu + X2U)(2/o + yiu + 3/2" + уз") как одноразовая задача, то лучше всего держать пари, что можно использовать очевидный метод с 12 умножениями и 6 сложениями, если, скажем, х и у, - не матрицы. Другая умеренно прийлекательная схема, требующая 8 умножений и 18 сложений, приведена в упр. 58, (Ь). Заметим, что если Хк фиксированы, когда уг изменяются, то (70) производит вычисления с 7 операциями умножения и 17 операциями сложения. Хотя даже эта схема не особенно пригодна в том виде, в котором она построена, наш вывод иллюстрирует важную технику, полезную в различных ситуациях. Например, Виноград воспользовался этим подходом для вычисления преобразования Фурье с помощью значительно меньшего количества операций умножения, чем необходимо для алгоритма быстрого преобразования Фурье (см. упр. 53).

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

Zq + ZiU + • + Zn-iu~

= (хо + xiu + • • • + x„ iu"-i)(yo + yiu + • • • + y„ iu"-i) modp(u). (71)

Здесь p{u) означает любой заданный нормированный полином степени п; в частности, р{и) может быть и" - 1, тогда одним результатом нашего исследования будет

нахождение ранга тензора, соответствующего циклической свертке степени п. Будет удобно записать р{и) в виде

р{и) = и" - pn-iu"-"------Piu-po. (72)

Таким образом, и" = ро+ piu + • • • + p„ iu"" (по модулю р{и)).

Элемент тензора tijk равен коэффициенту и* в mod р{и) и равен элементу в строке г и столбце к матрицы Р, где

/О 1 О ... Q \ О О 1 ... О

О О О ... 1 \ро Pi Р2 •• Pn-l/

(73)

называется сопровождающей матрицей р{и). (Индексы г, j, к в нашей ситуации пробегают значения от О до п - 1, а не от 1 до п.) Тензор удобен для транспонирования, если Tijk = tikj -частные слои {Tijk) для = О, 1, 2, ..., п - 1 просто заданы матрицами

I Р Р2 рп-1 (74)

Первые строки матриц в (74)-это соответственно единичные векторы (1,0, 0,...,0), (0,1,0,...,0), (0,0,1,...,0), (0,0,0,...,1); следовательно, линейная комбинация YlIZo Vk Р* будет нулевой матрицей тогда и только тогда, когда все коэффициенты Vk равны нулю. Кроме того, большинство этих линейных комбинаций в действительности - невырожденные матрицы, для которых

(wo,Wi,...,iu„ i)?;;tP* = (0,0,...,0)

тогда и только тогда, когда v{u)w{u) = О (по модулю р{и)),

Tj\ev{u) - vo+viu-{-----\-Vn-iu"~ hw{u) = wq+wiuH------Wn-iw"~- Таким образом,

2=0 VkP является невырожденной матрицей тогда и только тогда, когда полином v{u) кратен некоторому множителю р{и). Сейчас мы готовы доказать требуемый результат.

Теорема W (Ш. Виноград, 1975). Пусть р{и) -нормированный полином степени п и его полное разложение на множители в данном бесконечном поле равно

p{u)=p,{u)\..pq{u)-. (75)

Тогда ранг тензора (74), соответствующего билинейным формам (71), равен 2п - q над этим полем.

Доказательство. Билинейные формы можно вычислить только c2n - q умножений в цепочке, используя правила (58)-(60) в соответствующем стиле. Таким образом, необходимо только доказать, что ранг г > 2п - q. Выше был установлен тот факт, что rank(T(y)fc) = п; следовательно, по лемме Т любая (п х г)-реализация {А,В,С) тензора {Tijk) имеет гапк(С) = п ("rank" в переводе означает "ранг".- Прим. перев.). Наша стратегия - снова использовать лемму Т для нахождения вектора {vq, vi,..., v„-i), который обладает следующими двумя свойствами.