i) Вектор {vo,vi,...,Vn-i)C имеет самое большее q + г - п ненулевых коэффициентов.

ii) Матрица у{Р) = Е"=о kP

Эти свойства и лемма Т доказывают, что q + г - п > п. Следовательно, тождество

г /п-1 N

1=1 V *-=о /

1=1 \ k=0

показывает, как реализовать тензор v{P) размера nxnx 1 ранга п с помощью q+r-n умножений в цепочке.

Для удобства можно предположить, что первые п столбцов матрицы С линейно независимы. Пусть D - такая матрица размера пхп, что первые п столбцов матрицы DC равны тождественной матрице. Наша цель будет достигнута, если существует линейная комбинация {vo,vi,... ,Vn-i) максимум q строк из D, что v{P) не вырожден; данный вектор удовлетворяет условиям (i) и (ii).

Поскольку строки D линейно независимы, неприводимый множитель рх{и) не может делить полиномы, соответствующие каждой строке. Пусть задан вектор

W - {W0,Wi,...,Wn-l),

covered(u;) означает множество всех А, такое, что w{u) не кратно рх{и). Можно найти линейную комбинацию v п w v + aw двух векторов, такую, что

covered(t; -- aw) = covered(t;) U covered(u;) (76)

для некоторого а, принадлежащего полю. Смысл этого состоит в том, что если А покрыты V или W, но не Обоими, то А покрыта v -f- aw для всех ненулевых а; если А покрыты обоими векторами г; и ги, но А не покрыта v -f- aw, то А покрыта v + /3w для всех Р ф а. Если проверить 5 -f- 1 различное значение а, то по крайней мере одно будет удовлетворять (76). Таким способом можно систематически строить линейную комбинацию самое большее q строк матрицы D, покрывающих все А для 1 < А < 5. I

Одним из наиболее важных следствий теоремы W является то, что ранг тензора может зависеть от поля, из которого получаются элементы реализации [А,В,С). Например, рассмотрим тензор, соответствующий циклической свертке степени 5; это эквивалентно умножению полиномов mod р{и) = - 1. Над полем рациональных чисел полным разложением р{и) согласно упр. 4.6.2-32 является (и - 1) х {и у? + иV). Таким образом, ранг тензора равен 10 - 2 = 8. С другой сто-

роны, полное разложение над действительными числами в терминах числа ф=\{1 + л/5) имеет вид {и - 1)(и фи1){и - ф~и + 1), поэтому ранг равен только 7, если допустить появление в А, В, С произвольных действительных чисел. При разложении над комплексными числами ранг равен 5. Этот феномен не имеет места для двумерных тензоров (матриц), где ранг можно определить, вычислив определители подматриц и проверив, не равен ли он нулю. Ранг матрицы не изменяется, когда поле, содержащее ее элементы, является вложенным в большее поле, однако ранг тензора может уменьшиться, когда поле становится большим.

В статье, в которой впервые была приведена теорема W [Math. Systems Theory 10 (1977), 169-180], Виноград идет дальше, показывая, что все реализации (71)

в 2n - 5 умножений в цепочке соответствуют использованию (59), когда q больше 1. Кроме того, он показал, что единственный метод вычисления коэффициентов х{и)у{и) с deg(x) -f deg(y) + 1 умножений в цепочке - это использование интерполяции или (58) с полиномом, который расшепляется на различные линейные множители в поле. Наконец, Виноград доказал, что метод вычисления х{и)у{и) mod р{и) с 2п - 1 умножений в цепочке, где 5 = 1, по существу, является (60). Этот результат справедлив для всех цепочек полиномов, если только они "нормальные". Виноград расширил свои результаты на полиномы от нескольких неременных в работе SICOMP 9 (1980), 225-229.

Ранг произвольных тензоров размера m х п х 2 в соответствующем большом поле определен Джозефом Яя (Joseph JaJa), SICOMP 8 (1979), 443-462; JACM 27 (1980), 822-830; см. также его интересное обсуждение коммутативных билинейных форм в работе SICOMP 9 (1980), 713-728). Однако проблема вычисления ранга произвольного тензора размера п х п х п над любым конечным полем является ЛР-полной [J. Hastad, Journal of Algorithms 11 (1990), 644-654].

Для дополнительного чтения. В этом разделе была кратко затронута очень большая область, в которой возникает множество прекрасных теорий. Значительно более исчерпывающий материал можно найти в книгах А. Бородина и Дж. Мунро [А. Borodin and I. Munro, Computational Complexity of Algebraic and Numeric Problems (New York: American Elsevier, 1975)]; Д. Бини и В. Пана [D. Bini and V. Pan, Polynomial and Matrix Computations 1 (Boston: Birkhauser, 1994)]; П. Бергиссера, M. Клаусена и М, Амина Чокролахи [Р, Biirgisser, М. Clausen, and М. Amin Shokrol-lahi, Algebraic Complexity Theory (Heidelberg: Springer, 1997)].

УПРАЖНЕНИЯ

1. [15] Каков "хороший" метод вычисления "нечетного" полинома

и{х) = U2n-na:="+ + uzn-ix"" + • • • + иц?

► 2. [М20] Вместо того чтобы вычислять и{х + хо) с помощью шагов HI и Н2, приведенных в разделе, обсудите применение правила Горнера (2), когда умножение и сложение полиномов используются вместо арифметики в области коэффициентов.

3. [20] Предложите метод, аналогичный правилу Горнера, для вычисления полинома от двух переменных 5j+j<„ ицхуК (Этот полином имеет (п -f- 1)(п -I- 2)/2 коэффициентов, и его "общая степень"" равна п.) Вычислите используемое вами количество операций сложения и умножения.

4. [М20] В разделе показано, что схема (3) превосходит правило Горнера, когда вычисляется полином с вещественными коэффициентами в комплексной точке z. Сравните (3) с правилом Горнера, когда и коэффициенты, и переменная z - комплексные числа. Как много (вещественных) умножений и сложений-вычитаний требуется для каждого метода?

5. [М15] Подсчитайте количество умножений и сложений, необходимых по правилу второго порядка (4).

6. [22] (Л. де Джонг (L. de Jong) и Я. Ван Лиивен (J. van Leeuwen).) Покажите, как можно улучшить шаги S1, ..., S4 алгоритма Шо-Трауба (Shaw-IVaub), вычисляя Джонг Л. С. (Jong, Lieuwe Sytse de) Ван Лиивен Ж. (van Leeuwen, Jan) Шо М. М. (Shaw, Mary Margaret) Трауб Ж. Ф. (IVaub, Joseph Frederick) только приблизительно \п степеней хо.

7. [М25] Как можно вычислить /Зо, , 0п, когда (6) имеет значение u{xo+kh) для всех целых к?

8. [М20] Факториальная степень х- определяется таким образом:

к\{1) =х{х-1)...{х-к + 1).

Объясните, как вычислить UnX- + + щх- + uo с максимум п умножениями и 2гг - 1 сложениями, начиная с ж и п + 3 постоянных и„, ..., ио, 1, п - 1.

9. [М25] (Г. Дж. Райзер (Н. J. Ryser).) Покажите, что если X - (xij) -матрица размера п X п, то

рет(х) = ;(-1Г--- п Е

1<г<п l<j<n

Суммирование осуществляется по всем 2" наборам ci, ..., б„, независимо равным О или 1. Подсчитайте количество операций сложения и умножения, требуемых для вычисления рет{Х) по приведенной формуле.

10. [М21] Перманент матрицы X = (xij) размера пхп можно вычислить следующим образом: начать с п величин хц, xi2, Для 1 < А; < п предположим, что () величин Aks вычислены для всех подмножеств множества S, {1,2, ...,п}, содержащих к элементов, где Aks = xij .. .Xkj,, суммируется по всем к\ перестановкам ji...jk элементов множества S; затем составляются все суммы вида

A(k+i)s = Ak(s\{j})X(k+i)j-

Мы получим рег(Х) = Ап{1.....„}. Сколько операций сложения и умножения потребуется

для этого метода? Сколько ячеек понадобится для временного хранения?

11. [М46] Существует ли какой-нибудь метод вычисления перманента обычной матрицы размера пхп, использующий менее 2" арифметических операций?

12. [М50] Каково минимальное количество умножений, неббходимых для получения произведения двух матриц размера пхп? Чему равен наименьщий показатель ш, такой, что 0(71""") умножений достаточно для всех е > О? (Найдите хорошие верхнюю и нижнюю грани как для малых, так и для больших п.)

13. [М23] Найдите преобразование, обратное обычному дискретному преобразованию Фурье (37), выразив F(ti,...,t„) в терминах значений /(.si,... ,Sn)- [Указание. См. уравнение 1.2.9-(13).]

► 14. [НМ28] (Быстрое преобразование Фурье.) Покажите, что с помощью схемы . (40) можно вычислить одномерное дискретное преобразование Фурье

f{s)= F{t)uj\ а; = е"/=", О < s < 2",

0<t<2>

используя арифметику комплексных чисел. Оцените число выполняемых арифметических операций.

► 15. [НМ28] п-е разностное отношение f{xo, xi,..., Хп) функции f{x) в п + 1 различных точках Хо, XI, Хп определяется формулой

f(xo, Xl, . . . ,Хп) = {f{xo, XI, . . . ,Xn-l) - f{xi, . . , Xn-l,Xn))/{xo - Xn)

для n > 0. Таким образом, /(жо, xi,..., x„) = I]=o/(*)/По<;<п,;#*;(* " Xj) -симметричная функция n + l аргументов, (a) Докажите, что f{xo,... ,x„) = /<"(&)/п! для