AOP_Tom2 (1021737), страница 220
Текст из файла (страница 220)
ЗО), чтобы В! = О и В ыз! = 1 для 1 < / < 2т. Более того, можно предположитгч что Бзо = О. Множество результатов сейчас имеет максимум т + 1 + 2 ' '"г([у/2) — 1) = пзз + 1 степеней свободы. (Ь) Любая закая цепочка полиномов с максимум т умножениями может гюходить нв одну из рассмотренных в п. (а) форм, но полагаем, что г(!) = (//2) — 1 для 1 < ! < 2гп+ 1. и не предполагаем, что /ззо = 0 или !9,0 ! —— 1 для ! > 3. Эта простая каноническая форма включает т + 2т параметров. Так, как аз пробегают все целые значения, и так, как мы проходим все цепочки, так и !Зь пробегает максимально 2 +з множеств значений по модулю 2.
Следовательно, и множество результатов такое же. Для того чтобы получить все 2" полиномов степени и с 0-1 коэффициентами, должно выполняться т' + 2т > и, (с) Присвоим т ! — [з/и) и вычислим хз, хз, ..., х"'. Пусть и(х) = и„,ег(х)х! э'! + + и! (х) х"'+ ио(х), где каждое и, (х) — полинам степени < т с целыми коэффициентами (значит, его можно вычислить, не увеличивая число умножений). Вычислим и(х) по правилу (2), как полинам от х"', с известными коэффициентами.
(Используемое число сложений приближенно равно сумме абсолютных значений коэффициентов. Таким образом, данный алгоритм эффективен на 0 — 1 полиномах. Петерсон (Расе«лап) и Стокмейер (8«ос1апеуег) предложили также другой алгоритлу, который использует около ьу2и умножений.) См. Б1СОМР 2 (1973), 60-66, а также 3. Е. 8атабе, ЯСОМР 3 (1974), 150-1о8; Л. Сапе, ЯСОЫР 24 (1995), 473-483. Аналогичные результаты относительно сложений приводятся в работах Вогосйп аууб Соек, ЯСОМР 5 (1976), 146-157; Жтезг апу) Ъап «)е Чу!е!е, !пб Ргос.
/,егсеге 8 (1979), 178-180. 43. Если о, = а„+ аь — шаг в некоторой оптимюзьной цепочке сложений лля и + 1, вычислим х' = хухь и р, = рьху + рз где р, = х' '+ . + х+ 1. Опустим окончательное вычисление х"~~. Одно умножение экономится, как только аь = 1, в частности когда у = 1 (см. упр. 4.6.3-31 с « = -). зу 44. Пусть ! = (18 и), и предположим, что х, х~у х4, ..., х предварительно вычислены. Если и(х) — нормированный полинам степени и = 2«и + 1, то его можно записать как и(х) = (х + + а)е(х) + иу(х), где с(х) и ш(х) — нормированные многочлены степени т. Здесь приведен метод для и = 2пю — 1 > 3, который требует дополнительно 2' — 1 операций умножения и 2ьы+ 2' ' — 2 операций сложения.
Если и = 2', то можно применить правило Горнера для уменьпуения и на 1. И если т = 2' < и С 2У«' — 1, можно записать и(х) = х о(х) + ш(х), где с и ш — нормированные полнномы степени и — т и т соответственно. Индукцией по ! можно показать, что потребуется максимум у и + ! — 1 умножений и 4 и сложений после предварительных вычислений. (См. 3, 1Ъ'!войта«1, !ВМ Тесй. Вйг!азате Вп!!. 13 (1970), 1133-1135.) Замечание. Можно также вычислить и(х), выполнив -'и+О(з/й) операций умножения и и + 0(ьгй) операпий сложения, по таким же обоснованным правилам, если необходимо минимизировать число умножений и сложений. Характерный для данного класса полинам руь„(х) = ((...
(Кх + па)(х'+'+ ууу) +ау)(ху+ + !уз) + аз) " ) (х" + Вь у ) + аь-у) (х' + у!0) "охватывает" коэффициенты при степенях (1,!+!«,1+1+(Й-1),...,!+!«+(!« — 1)+ +(уу Ь1), т' — !1, ги' — й + 1,..., т — 2), где т'=т+!+(!+1)+. +Ь=уи+( ) — ( ). Сложив такие полиномы ры,(х), ры.„,(х), ..., ргь „(х) для ту = ( з ) + ( у ) получим произвольный нормированный полинам степени йу + й + 1.
[В статье Ка)у!и юн1 Чу!лоб«ад, Сошт. оп Риге апу! Арр!!е«! Ма«Ь. 25 (1972), 433-458, 52, доказано, что конструкция с -'и + О(!оба) умножениями и < (1 + «)и сложениями возможна для всех «> О, если и достаточно большое.] 45. Достаточно показать, что ранг (Т„ь) не больше, чем ранг (!оь), так как можно получить (!аь) из (Ту«), преобразовав его таким же способом с Р ', С ', Н ', Если !оь = ) у" у а,уЬрсы, то немедленно следует, что Ту« = 2т" у<у<„(~, у Р„а, у)(2 ",, Сы Ь, у)(т „', у Ньь сьч).
(Г. цу, де Гроот (Н. Р. у)е Сгооге) доказал, что все нормальные схемы, которые дают произведение матриц размера 2 х 2 в результате семи умножений в цепочке, эквивалентны в том смысле, что их можно получить одну из другой, выпазнив умножение на невырожденную матрицу, как в данном упражнении.
В этом смысле алгоритм Штрассена (Зггэзэеп) единственный. См. ТЬеог. Сагир. Яс!. 7 (1978), 127-148.) 46. Согласно упр. 45 можно добавить любое кратное строке, столбцу или матрице к другой строке, столбцу или матрице без изменения ранга; также можно умножить строку, столбец или матрицу на не равнух! нулю константу или транспонировать тензор.
Всегда можно найти последовательность операций, которая приводит данный тензор размера 2 х 2 х 2 к одной из таких фор ( ) (оо) (! о) (ов) (! ) ( о) (! о)(о ) (! ) ( ) По р последний тензор имеет ранг 3 или 2 в зависимости ог того, сколько неприводимых множителей имеет !юлином и — ги — 9 (один или два) в интересующем нас поле (см. (74)). г 47. Тензор размера т х и х в имеет гнив степеней свободы. Согласно упр. 28 все тензоры размера ги х и х в можно выразить в терминах (т + и + в)г элементов реализации (А,В,С), кроме с!гучаев, когда (т+ и+ в)г > тив. С другой стороны, предпалажим, что т > и > в. Максимальный ранг матрицы размера т х и равен и. Таким образом, люжна получить любой тензор за ив умножений в цепочке, п!ьлучая отдельно каждую матрицу.
(В упр. 46 показано, что такая нижняя грань для максимального ранга тензора не является наилучшей возможной гранью и верхней гранью. Томас Д, Хаузл (ТЬогпаз П. Но»е!1, РЬ П. 1Ьев!з, Согпей Сп!»., 1976) показал, чта существуют тензоры, имеющие ранг > ] тив/(т + и -!- в — 2)] иад комплекснылги числами.] 48.
Если (А, В, С) и (А', В', С') — - реализации (!иг) и (!'„г) длиной г и г' соответственно, реализации (г„!) и (1" ,ь) длиной г+ !.' и г г соответственно Замечание. Многие, естественно, предполагают, что гапЬ((цгг) ~ (г(гг)) = гапЬ(й,гь) + гану(!( ь), однако и упр. 60, (Ь) и 65 показано, что это выглядит менее правдоподобным, чем кажется. 49. Согласно лемме Т гапЬ(гив) > гапЬ(гцгг!) Обратно, если М вЂ” матрица ранга г, та ее можно преобразовать с помощью операций са строками и столбцами, найдя такие невырожденные матрицы Г и С.
что матрица РМС будет содержать все О, за исключением г диагональных элементов, равных 1 (см. алгоритм 4.6.2!в!). Следовательно, ранг тензора РМС < !. и он такой же, как ранг тензора М согласно упр. 45. 50. Пусты = (!', гв), где 1 < !' < т и 1 < гв < и, тогда !<в в Нг — — б, гб, г„.. Очевидно, что гап!г(г,<гг!) = ти, так как (!цгг!) — матрица перестановок, По лемме 1. сапу(1,гв) > ти. Обратно, так как (гчв) имеет всего ти ненулевых элементов, та. очевидна, ее ранг < гии. (Существует, следовательно, ненормальная схема, требующая менее ти явных умножений. Подобной анормальной схемы не существует (Солил.
Риге апс! Арр!. Магй. 3 (1970), 165-179], Но мажет быть достигнута некоторая экономия, если тахая же матрица используется с в > 1 различными вектор-столбцами, поскольку это эквивалент умножения матриц размера (и х в) и (т х и)). (а) в! УО '!" У! вг Уо У! нг! г (хо + х!)в! игг — г(хо х!)гг; вго = пг! + гпг, ! ш! = т! — тг. (Ь) Здесь несколько промежуточных шагав, использующих методику из раздела: ((хо — хг)+ (х! — хг)и)((уо — уг)+(у! — Уг)и) та!1(и +и+1) = ((хо — хг)(уо — уг)— (х! — хг)(у! — Уг)) + ((хо — хг)(уо — Уг) — (х! — хо)(у! — Уо))и. Первая реализация— 1011, 1011, 1121 х-.
Вторая реализация— 1121 х †, 1101 , 1011 Окончательно алгаритг! вычисляет в! = Уо + у!, вг = уо — уг, вв = уг — уо, в! = Уг — уг, вг = в! + Уг; т! — — в(хо+ х! + хг)вв, тг = г(хо+ х! — 2хг)вг, тг = 5(хо — 2х! + хг)вв, ! ! ! т4 = 3(-2яо + х! + зг)34! 1! = т! + тв, 32 = т! — тз, 33 = т! + тз, юо = 1! — тв, ! п4! = 33 ! 4и4 и!2 = 32 п34. 52.
Пусть 14 = (к', й"), когда к тоб и' = 44' и к теди" = к". Нужно вычислить св!»,» ! = хб о !Рс, ! >, где сУммиРование пРоизводитса так, что ! + У ж Н (по модУлю и') и !'! + ув аз 4св (по модулю ив). Это можно сделать, применив алгоритм и' к 2и векторам Х, и 1;. длиной ив и получив и' векторов И'» . Каждое векторное сложение становится и сложениями, каждое умножение параметров становится и умножением параметров и каждое умножение а цепочке векторов заменяется циклической сверткой степени и".
[Если в подалгоритмах испазьзуется минимальное число умножений в цепочке над рациональными числами, то в этом алгоритме используется на 2(и' — с2(и)) (ив — Ы(ив) ) операций балыке минимального числа, с((и) — число делителей и, что следует из упр. 4.6.2— 32 и теоремы 1Ч.] 53.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
