AOP_Tom2 (1021737), страница 155
Текст из файла (страница 155)
ренно привлекательная схема, требующая 8 умножений и 18 сложений, приведена в упр, 58, (Ь). Заметим, что если х! фиксированы, когда у! изменяются, то (70) производит вычисления с 7 операциями умножения и 17 операциями сложения. Хотя даже эта схема не особенно пригодна в том виде, в котором она построена, наш вывод иллюстрирует важную технику, полезную в различных ситуациях. Например, Виноград воспользовался этик! подходол4 для вычисления преобразования Фурье с помощью значительно л!еньшего количества операций умножения, чем необходимо для алгоритма быстрого преобразования Фурье (см. упр. 53).
В завершение этого раздела найдем точный ранг тензора размера п х и х п, который соответствует умножению двух полиномов по модулю третьего: го+2!и+ ° +2 !и" ! = (хо + х! и + + х„! и" 1)(уо + у! и + + у„! и" ') шоб р(и). (71) Здесь р(и) означает любой заданный нормированный полинам степени и; в частности, р(и) может быть и" — 1! тогда одним результатом нашего исследования будет нахождение ранга тензора, соответствующего циклической свертке степени и. Будет удобно записать р(и) в виде Р(п) =«" — р — и" ' —" — Р1н — Ре.
(72) Таким образом, и" = Ре + р1и+ + рк .1и" 1 (по модулю р(и)). Элемент тензора 1„ь равен коэффициенту и~ в и"э' шойр(и) и равен элементу в строке 1 и столбце 1. матрицы РУ, где О 1 0 ... 0 0 0 1 ... 0 (73) 0 О 0 ... 1 РО Р1 Рэ ° Рк — 1 называется сопровождающей матрицей Р(и). (Индексы 1, у, й в нашей ситуации пробегают значения от 0 до и — 1, а не от 1 до и.) Тензор удобен для транспонирования, егли Тпв = гм — - частные слои (Тбь) для й = О, 1, 2,..., и — 1 просто заданы матрицами р р2 Рк — 1 (74) Первые строки матриц в (74) — это соответственно единичные векторы (1,0, О ,0), (0,1,0,...,0), (0.,0,1,...,0), ..., (0,0,0,...,1): следовательно, линейная комбинация 2 ~ е кь Рь будет нулевой матрицей тогда и только тогда, когда все коэффициенты иь равны нулю.
Кроме того, болыпинство этих линейных комбинаций в действительности — невырожденные матрицы, для которых (ше,юм..., ~и„1) ~~~ ехР = (0,0,...,0) к=о тогда и только тогда, когда е(и)ш(и) = 0 (по модулю р(и)), где к(и) = ке+к1и+. +к„1и" 1 и н)(и) = юе+ш1н+ +ю„1и" '. Таким образом, к — 3 2 ь е иь Р является невырожденной матрицей тогда и только тогда, когда полинам е(и) кратен некоторому множителю р(и). Сейчас мы готовы доказать требуемый результат. Теорема Ж (Ш. Виноград, 1975). Путгь р(и) --- нормпроканный полнном степени и гг его полное разложение на множители к данном бесконечном поле равно (75) Р(н) = 1Л(н) ' - . Рэ(н) '.
Тогда ранг тензора (74), соответствующего билинейным формам (71), ракен 2п — о над этом полем. Доказптельсгпко. Билинейные формы можно вычислить только с 2п — д умножений к цепочке, используя правила (58)-(бО) в соответствующем стиле. Таким образом, необходимо только доказать, что ранг г > 2п — д. Выше был установлен тот факт, что гавдос(ТОрь) = и; следовательно, по лемме Т любая (и х г)-реализация (А,В,С) тензора (Т, ь) имеет гапк(С) = п (ктапк" в переводе означает "ранг".— Прим, перев.), Наша стратегия — снова использовать лемму Т для нахождения вектора (ке, ем..., е„1), который обладает следующими двумя свойствами, 1) Вектор (ео, еы..., е„~)С имеет самое большее о + г — и ненулевых коэффициентов, й) Матрица е(Р) — ~ " ', Рь Эти свойства и лемма Т доказывают, что д + г — и > и.
Следовательно, тождество показывает, как реализовать тензор и(Р) размера и х и х 1 ранга п с помощью у+г — и умножений в цепочке. для удобства можно предположить, что первые и столбцов матрицы С линейно независимы. Пусть 0 — такая матрица размера и х и, что первые и столбцов матрицы РС равны тождественной матрице. Наша цель будет достигнута, если сушествует линейная комбинация (еэ, им..., и„~) максимум д строк из О, что и(Р) не вырожден; данный вектор удовлетворяет условиям (~) и (0). Поскольку строки )2 линейно независимы, неприводимый множитель рл(и) не может делить полиномы, соответствующие каждой строке. Пусть задан вектор согегеб(ю) означает множество всех Л, такое, что ш(и) ве кратно рх(и). Можно найти линейную комбинацию е и ю е+ ав двух векторов, такую, что согегео(е + ав) = согегеп(е) О сочегей(ш) (76) для некоторого а, припал,лежащего полю.
Смысл этого состоит в том, что егшн Л покрыты е или ш, но не обоими, то Л покрыта в + пш для всех ненулевых сб если Л покрыты обоими векторами и и ш, но Л не покрыта е+ агэ, то Л покрыта и +,6ш для всех Д ф а. Если проверить д + 1 различное значение о, то по крайней мере одно будет удовлетворять (76). Таким способом можно систематически строить линейную комбинацию самое большее д строк матрицы Р, покрывающих все Л для 1 < Л < д. э Одним из наиболее важных следствий теоремы % является то, что ранг тензора может зависеть от поля, из которого получаются элементы реализации (А,В,С).
Например, рассмотрим тензор, соответствующий циклической свертке степени 5; это эквивалентно умножению палиномов шод р(и) = иэ — 1. Над полем рациональных чисел полным разложением р(и) согласно упр. 4.6.2-32 является (и — 1) х (и~ + па+ и~ + и+ 1). Таким образом, ранг тензора равен 10 — 2 = 8. С другой стороны, полное разложение над действительными числами в терминах числа 4 = -'(1+ ~/5) имеет вид (и — 1)(и~ + пи + 1)(и — ф 'и + 1), поэтому ранг равен только 7, если допустить появление в А, В, С произвольных действительных чисел. При разложении над комплексными числами ранг равен 5.
Этот феномен не имеет места для двумерных тензоров (матрнц), где ранг можно определитгч вычислив определители подматрнц и проверив, не равен ли он нулю. Ранг матрицы не изменяется, когда поле, содержащее ее элементы, является вложенным в большее поле, однако ранг тензора моисею уменьшиться, когда поле становится большим. В статье, в которой впервые была приведена теорема % [Маэп. Яуэсешэ Тбсогу 10 (1977), 169-180), Виноград идет дальше, показывая, что все реализации (71) в 2п — д умножений в цепочке соответствуют использованию (59), когда а больше 1.
Кроме того, он показал, что единственный метод вычисления коэффициентов х(и)р(и) с Йеб(х) + г(еб(р) + 1 умножений в цепочке — это использование интерполяции или (58) с полиномам, который расщепляется на различные линейные множители в поле. Наконец, Виноград доказал, что метод вычисления х(и) у(и) шаб р(и) с 2п — 1 умножений в цепочке, где а = 1, по существу, является (60). Этот результат справедлив для всех цепочек полиномав, если талька они "нормальные". Виноград расширил свои результаты на палиномы от нескольких переменных в работе ЯСОЛ!Р 9 (1980), 225 — 229. Ранг произвольных тензоров размера т х п х 2 в соответствующем большом поле определен Джозефом Яя (,1оверЬ,!а',!а'), 5!СОА!Р 8 (1979), 443 — 462;,ИСМ 27 (1980), 822 — 830; см. также его интересное обсуждение коммутативных билинейных форм в работе 8!СОМР 9 (1980), 713 — 728).
Однако проблема вычисления ранга произвольного тензора размера и х п х и над любым конечным полем является А?Р-полной [1. Навсаб, Юонгпв! оЕА!бог!ВЬтв 11 (1990), 644 — 654[. Для дополнительного чтения. В этом разделе была кратко затронута очень большая область, в которой возникает множество прекрасных теорий. Значительно более исчерпывающий материал можно найти в книгах А. Бородина и Дж. Мунро [А.
Вагогйп апб 1. Манго, Сотригагюпв! Сотр!ех!гу оГА!8ебга!с апс( !внтег!с Ргаб!етв (Хеч Уаттс: АтеПсап Е!вет!ег, 1975)[; Д, Бнни и В. Пана [П. Вш! апб У, Рап, Ро!упот!а! апб Ма!Пх СотрнгаНопв 1 (Воз!оп: В!гЬЬанвег, 1994)]; П. Бергиссера, М. Клаусена и М. Амина Чокролахи [Р. Вбгб!ввег, М. С!анвеп, апс! М. Аппп ВЬоЬго1- (аЫ, А!беЬга!с Сотр)ехйу ТЬеогу (Не!с(е!Ьегб: Брг!пбег, 1997)). УПРАЖНЕНИЯ 1. [15[ Каков "хороший" метод вычисления "нечетного" палинама и(х) = ив„+~я + ив„~х + + и~х. вп.~-! вн-1 ? 2. [МхйО[ Вместо того чтобы вычислять и(х + хв) с помощью шагав Н1 и Н2, приведенных в разделе, обсудите применение правила Гарнера (2), когда умножение и сложение палиномов иапальзуются вместо арифметики в области коэффициентов. 3. [хО) Предложите метод, аналогичный правилу Горнера, для вычисления полинама от двух переменных ~,+,<„иих'р'.
(Этот полинам имеет (и+1)(п+ 2)/2 коэффициентов, и его "общая степень" равна и.) Вычислите используемое вами количество операций сложения и умножения. 4. [мвО) В разделе показано, чта схема (3) превосходит правило Гориера, когда вычисляется полинам с вещественными коэффициентами в комплексной точке х. Сравните (3) с правилом Гарнера, когда и коэффициенты, и переменная х — комплексные числа. Как много (вещественных) умножений и сложений-вычитаний требуется для каждого метсда? б. [М1О) Подсчитайте количество умножений и сложений, необходимых по правилу второго порядка (4). б. [вв) (Л. де Джонг (Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
