билинейные формы, и транспонированный тензор, понятно, имеет такой же ранг, но соответствующие билинейные формы являются, в принципе, совершенно иными. Например, нормальная схема вычисления произведения матрицы размера {т х п) на матрицу размера (п х s) предусматривает существование нормальной схемы вычисления произведения матрицы размера (п х s) и матрицы размера (sxm), если используется такое же число умножений по цепочке. В терминах матриц эти две проблемы едва ли кажутся как-то связанными - они включают различное число умножений на векторы различной размерности, но в тензорной терминологии они эквивалентны. [См. В. Я. Пан, Успехи мат. наук 27,5 (сентябрь-октябрь 1972), 249-250; J. Е. Hopcroft and J. Musinski, SICOMP 2 (1973), 159-173.]

Если тензор {tijk) можно представить в виде суммы (51) г одноранговых тензо-рови А, В, С - матрицы (аи), (bji), (сы) соответствующего размера тх г, пхг, sxr, то мы говорим, что {А,В,С) - реализация тензора {kjk). Например, реализация умножения матриц размера 2 х 2 в (52) может быть точно определена матрицами

/1 О 1 00 1 1\ 0 100010 0010111

Vo О О 1 1 I l/

/1 О О 1 1 О 1\ 0 10 10 0 0

о о 111 о i Vo о 11 о 11

/1 1 о о о о 0\ 10 110 0 1 10 0 0 111

Vl о 1 о 1 о i/

(53)

Тензор {tijk) размера т х п х s также можно представить в виде матрицы, объединив ее индексы. Обозначим {t(ij)k) для матрицы размера тп х s, строки которой указаны парами индексов (г, j), а столбцы имеют индекс к. Аналогично (tkiij)) станет матрицей размера s х тп, содержащей tijk в строке А: и в столбце ; {t{ik)j) является матрицей размера ms х п и т. д. Индексы матрицы - необязательно целые числа, и здесь упорядоченные пары используются как индексы. С помощью этих обозначений можно получить следующую простую, но полезную нижнюю грань ранга тензора.

Лемма Т. Пусть (А, В, С) -реализация тензора {tijk) размера т х п х s. Тогда гапк(А) > Tank{tiijk)), гапк(В) > Tank{tjik)) игапк(С) > iank{tk(ij)); следовательно,

iank{tijk) > max(rank(ti(j<;)), rank(tj(ifc)), Tank{tk(ij))).

Доказательство. Из соображений симметрии достаточно показать, что г >гапк(А) > Tank{ti(jk) ) Так как матрица А имеет размер m х г, то, очевидно, она не может иметь ранг, больший, чем г. К тому же согласно (51) матрица {ti(jk)) равна AQ, где Q - матрица размера г х ns вида Qi{j,k) = bjiCki. Если х - любая вектор-строка, такая, что хА = О, то xAQ = 0. Следовательно, все линейные зависимости в А появляются и в AQ и rank(AQ) < гапк(А).

В качестве примера использования леммы Т рассмотрим проблему умножения полиномов. Предположим, необходимо умножить обычный полином степени 2 на обычный полином степени 3, вычисляя коэффициенты произведения:

(хо -Н XiU + Х2и){Уй + yiU + У2и + Уз")

= 20 -Н ZiU -Н 22u -Н ZsU -Н Ziu -Н ZbU. (54)

Это сводится к проблеме вычисления шести билинейных форм, соответствующих тензору размера 3x4x6:

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

0 100 10 0 0 0 0 0 0

0 0 10 0 10 0 10 00

/0 0 0 1 00 10 Vo 1 00

/О о о 0\ 0 0 0 1

Vo о 1 о/

0 0 0 0 0 0 0 0 0 0 0 1

(55)

Для краткости можно записать (54) в виде х{и)у{и) = z{u), где х{и) - полином Хо + xiu + X2u я т. д. (Мы замкнули круг, вернувшись к началу данного раздела, но в отличие от (1), где полином обозначается как и{х), мы обозначаем его как х{и); мы изменили обозначения, потому что сейчас нас интересуют переменные коэффициенты полиномов.)

Если каждую из шести матриц в (55) рассматривать как вектор размерности 12 с индексами то ясно, что векторы линейно независимы, так как их нули

занимают разные позиции. Следовательно, по лемме Т ранг (55) равен по крайней мере шести. Обратно, можно получить коэффициенты zq, z\, zs только с помощью шести цепочек умножений. Например, вычисляя

х(0)у(0), х(1)у(1), х(5)у(5)

(56)

при заданных значениях z(0), л(1), ..., z(5) и по интерполяционной формуле, приведенной выше, получим коэффициенты z{u). Вычисление x{j) и y{j) можно выполнить всецело в терминах сложений и/или умножений параметров, и интерполяционная формула просто использует линейные ко.мбинации этих значений. Таким образом, все цепочки умножений показаны в (56), а ранг (55) равен шести. (По существу, здесь используется та же техника, что и при умножении чисел с большой точностью в алгоритме 4.3.3Т.)

Оказывается, реализация {А, В, С) (55), набросок которой приведен в данном разделе выше, имеет вид

/1111 1 1\

0 12 3 4 5 Vo 1 4 9 16- 25/

/1 1 1 О 1 2

1 1 1ч 3 4 5 0 14 9 16 25 Vo 1 8 27 64 125/

/ 120 -274

О О О О Оч

600 -600 400 -150 24

225 -770 1070 -780 305 -50

-85 355 -590 490 -205 35

15 -70 130 -120 55 -10 ,

V -1 5 -10 10 -5 1/

420-

(57)

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

Во-первых, чтобы вычислить коэффициенты х{и)у{и), когда deg(a;) = m и deg(y) = п, можно воспользоваться тождеством

х{и)у{и) - {х (и) у (и) mod р{и)) + ХтУпР{и),

(58)

где р{и) - любой нормированный многочлен степени т п. Полином р{и) следует выбрать так, чтобы коэффициенты х{и)у{и) modp(u) легко вычислялись.

Во-вторых, чтобы вычислить коэффициенты х{и)у{и) modp(u), когда полином р{и) может быть множителем q{u)r{u), где gcd(5(u), r(u)) = 1, следует воспользо-

ваться тождеством

х{и)у{и) modq{u)r{u) = [а{и)г{и){х{и)у(и) modq{u))

+ b{u)q{u){x{u)y{u) mod r(u))) mod q{u)r{u), (59)

где a{u)r{u) + b{u)q{u) = 1; это, no существу, применение к полиномам китайской теоремы об остатках.

В-третьих, всегда можно вычислять коэффициенты полинома x{u)y{u)modp{u), используя тривиальное тождество

х{и)у{и) mod р{и) = (х(и) modp(u)) (у(и) modp(u)) modp(u). (60)

Повторно применив (58)-(60), можно, как будет показано ниже, получить эффективную схему.

Например, для задачи (54) выберем р{и) = - и и применим (58); основания для такого выбора р{и) будут приведены в дальнейшем. Если записать р{и) = и{и - 1), правило (59) приведет к

х{и)у{и) mod и{и - 1) = (-("* - 1)а;оуо + и*{х{и)у{и) mod {u - 1)))

mod(u-u). (61,

Здесь использован тот факт, что х{и)у{и) mod и = хоУо] вообще, это хорошая идея - выбрать р{и) так, чтобы р(0) = О, поэтому можно использовать данное упрощение. Если сейчас удастся определить коэффициенты wq, wi, Ш2, ws полинома х{и)у{и) mod (и* - 1) = гио -I- wiu -Н гигп + wsu, то задача будет решена, поскольку

и* (x(u)y(u) mod (u* - 1)) mod (u - u) = wqu* +wiu + wv + wzu,

и комбинация (58) и (61) приведет к

х{и)у{и) = ХоУо + {wi - Х2Уъ)и -\- W2U + WzU -- {wq - ХоУо)"* + Х2УъУ (62)

(Конечно, эту формулу можно проверить непосредственно.)

Остается решить проблему вычисления х{и)у{и) mod (и* - 1) (эта небольшая задача интересна сама по себе). На минутку допустим, что полином х{и) имеет степень 3,а не 2. Тогда коэффициенты х{и)у{и) mod (и* - 1) равны

ХоУо + XiJ/s + Х2У2 + ХЗУ1, Xoyi + Х1У0 + Х2УЗ + Х3У2,

Х0У2 + Х1У1 + Х2У0 + Х3У3, хоуз + з:1У2 -Н Х2У1 + хзуо и соответствующий тензор равен

/1 0 0 0\ 0 00 1 0010,

\0 1 О О/

/О 1 О 0> 1000 0 0 0 1

\0 О 1 О/

/О О 1 0\ /О о о 1\

0 100 00 10

1000 0 100

\0 0 0 1/ \1 0 0 0/

(63)

Вообще, когда deg(a;) = deg(y) = n - 1, коэффициенты х{и)у{и) mod (u"-l) называют циклической сверткой {xo,xi,... ,Xn-i) и {yo,yi,... ,yn-i)- к-й коэффициент Wk является билинейной формой YliVj ""Д сумма берется по всем г и j с г -f- j = А; по модулю п.

Циклическую свертку степени 4 можно получить, применив правило (59). Первым шагом будет нахождение множителей и*-1, т. е. (u-l)(u--l)(u-l-l). Это можно