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