Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 50
Текст из файла (страница 50)
Постройте эффективные алгоритмы для циклической и отрицательной циклической сверток для целых чисел, когда и — степень 2. Вази алгоритм полностью должен обходиться целыми числами, и должно выполняться максимум О(п!оба) умножений и максимум О(п!обп!о81обп) сложений, вычитаний или делений четных чисел на 2. (Указанпе. Цю клическая сверчка порядка 2п может быть сведена к циклической и отрицательной циклической свертке порядка и, есди воспакьзоваться (59).) 60. (М87] (В.
Я. Пан.) Задача умножения матрицы размера (ш х и) на матрицу размера (и х з) соответствУет тензоРУ (е!е»В л >ы, >) РазмеРа плп х пэ х эт, где еоа >!> и>!л, > —— - 1 тогда и талька тогда, когда б = л, >' = >' и Й' = й. Ранг этого тензора Т(т,п,з) равен наименьшему числу г, такому, что числа а, >, Ь.л >, ем, существуют и удовлетворяют соотношению х у>л*ы = ) ~ ~ аочхц ) ( ~ б>лчу,л ) ~ ~ сл,асье). ><><» ~ <,<, 1<у<» 1 <л < ~<»'<» ~«л<» ~« ' ~< й» ~ <1< 1<лб» Пусть М(п) — ранг тензора Т(п, и, п). Назначение упражнения — использовать симметрию такого трилинейного представлении для эффективного вычисления реализации умножения матриц, элементы которых — целые числа, когда гл = и = э = 2и.
Для удобства разделим индексы (1,...,п) надва подмножества О = (1,3,...,п — Ц и Е = (2,4,...,п) с и элементами в каждом н установим взаимно однозначное соответствие между подмножествами О н Е по правилу: л = 1+ 1, если л 6 О, л = л — 1, если 1 6 Е. Таким образом получаем е = 1 для всех индексов Ь а) Из тохсдества абс+ АВС м (а+ А)(Ь+ В)(с+ С) — (а+ А)ЬС вЂ” А(Ь+ В)с — аВ(с+ С) следует, что хо Улиты = ~~' (хц + х»>НУ>л + у»)(злю + ху») — Е> — Ег — Ез, 1умх,лй бад>ез где Е = ЕхЕхЕ О ЕхЕхО Е> ЕхОх Е 1> ОхЕхŠ— -множество всех тройных индексов, включающих максимум один нечетный индекс; Е~ — -сумма всех членов вида (х, + хы)у »хуа лля (Еу, Ь) б Е и Ез, Ез — подобные суымы членов ха>(уз» + уц)зло х; уц(хы + згз), Ясно, что Е имеет 4и = -и членов.
Покажите, что каждую з 1 з из сумм Ем Ел, Ез можно реализовать как сумму Зл трилинейиых членов; кроме 2 того, если Зя тройных индексов вида (л, л,а), (л, 1,1) и (>,1, л) не содержатся в 5, можно 58. (НМ88( (а) Покажите, что любая реализация (А, В,С) текюра умножения полиномов (55) должна иметь следующие свойства: любая ненулевая линейная комбинация трех строк матрицы А должна быть вектором по крайней мере с четырьмя ненулевыми элементами н любая ненулевая комбинация четырех строк матрицы В должна иметь по крайней мере три ненулевых элемента. (Ь) Найдите реализацию (А,В,С) (55), которая использует в качестве элементов только О, +1 и -1, где г м 8.
Попытайтесь использовать настолько много нулей, насколько это возможно. э 89. (М49( (П Ж. Нуебаумер (Н. 3. НпяЬапшет), 1980.) В разделе определено, что циклическаясверткадвух последовательностей (хе,х>,...,х„>) и (уо,уа,,у ~) — это последовательность (хс>х>, -,х» >), где хл =хоул+ +хира+х>е>у ->+. ° +х ~ул ь Аналогично определим атрвцагаслькую циклическую сасргаку, но с модифи««кровать Ем Е«н Ез таким способом, что тождество останется справедливым без добавления каких-нибудь новых трилинейных членов.
Следовательно, М(п) < -и + Лп — уг«, когда и четное. з ««« Ь) Используйте метод (а), чтобы показать, что две на«авион««мв задачи умножения матриц размера т х и х в можно выполнить с тпв + тп+ ив+ вт некоммутативными умножениями. 61, [М26) Пусть (Ь «)- — тензор нвд произвольным полем. Определим гапйв(16«) как минимальное значение г, такое, что существует реализация вида а аа(и)бд(и)са(и) =зм«й+0(и + )„ 1-1 где аа (и), Ьд(и), см(и) --полиномы от и нед полем. Таким образом, гап)со — обычный ранг теизора.
Докажите, что а) гел!«з+1(«, «) < га«йв(Ь «); Ь) гый(««з«) < ( з) гапЬв(«; «); с) гыйв((«о«) !5 («б«)) < гап!«в(«и«) +гавйв(Г( «) в смысле упр. 43; «!) гап)с««з*((«и«) з («'„«)) < гыйв(«ь«) гщйв («о«); е) гмйз«з ((ГЗ«) 4«(Г',1«)) < гапйг(г(Г'; «)), где г = га«йв(ГО«) и тТ означает прямую сумму Т Ю «и Т «.
копий Т. 62. [МЯЛ) Гранью ранга тензор» (й «), обозначенной через гы«)«(Ф««), называется пппв>«гап1«в(«з«), где гапЬв определен в упр. 51. Докажите, что тензор (а а) (е ' ) имеет ранг 3, но грань ранга 2 нзд каждым полем. 63. [НИХ) Пусть Т(т, и, в) — тензор умножения матрицы, как в упр. 60, и пусть М(Х)— р Т(Х,Х,Х). а) Покажите, что Т(т,п,,в) ЗТ(М,Х,Я) = Т(тЛ«,нХ,«Я). Ь) Покажите, что гапйв(Т(тХпХвХ)) < гепЬ«(М(Х)Т(т,п,в)) (см, упр, 61, (е)). с) Если Т(т, и, в) имеет ранг < г, покажите, что ЛТ(Х) ы О(Х~«~'"зз!) при Х -«оо, где ю(т,н,в,г) = 3!обг/!обтпз.
«!) Если грань ран«атензораТ(т„г«,в) < г, покажите, что М(Х) = О(Х"«~'"вв!(!обХ) ). 64. [МУО] (А. Шенхаге (А. ЯсЬопЬабе).) Покажите, что гап)с«(Т(3,3,3)) < 21, так как М(Х) ы О(Х«гз) «65. [М27) (А. Шбнхаге.) Покажите. что тай«(Т(«и,1, и) Ж Т(1, («п-1)(п-1), 1)) = тп+ 1. Указание. («ассмотрите трилинейную форму ««« (к, + иЛ6)(р« + изб)(я+ изз, ) — (к«+. +к,)(р1 + + р„)Е„ ««1*~« когда Л,. -, Х« = 2„" «К.
ы О. 66. [И«/УЗ) Воспользуйтесь результатом упр. 65 для уточнения асичптотических граней нз упр. 63. а) Докажите, что существует предел «« = !!«««„««1об М(п)/!об и. Ь) Докажите неравенство (тпз)"~~ < гав!«(Т(п«,п, в)). с) Пусть « — тензор Т(т,п,в) 51 Т(М.Х,Я). Докажите, что (тпз)~~~+ (ЛХХЯ)"~~ < уагй(«). Указание. Рассмотрите прямое произведение «с самим собой.
«!) Докажите, следовательно, неравенство 1б ~в + 9 Гз < 17 и получите, что ««< 2.55, 67. (НМ40) (Д, Копперсмит (П. СорретэштсЬ) н Ш. Виноград.) Обобщал упр. 63 и 66, можно получить даже лучшую верхнюю грань ы. а) скажем, тензор (й!4) является невмрозтсденнм»4, если тюй(11! тп) и т, галь(1!тд1!) = и и гшть(сэ!!1!) = з в обозначениях леммы т. Докажите, что тензор т(ш,и,з) для умножения матриц размера тии х пз является невырожденным.
Ь) Покажите, что прямая сумма нееырожденных тензоров является невырожденной. с) Тензор 1 размера гл х и х з с реализацией (А, В, С) длиной г называетсл допусками!им улучшение, если он невырождеи и существуют ненулевые элементы 4, ..., д„такие, что 2 !" ! ааЬ!!4 = 0 для 1 < 1 < ти и 1 < у < и. Докажите, что в подобном случае грань ранга Г 8 Т(1, 9, 1) < г, где 9 = г — пт — и, Указаны. Существуют матрицы 1' и )4' размера д х г, такие, что 2; ! епЬ!14 = 2; ! аашр4 = 0 и ~ ! 1 эаш!!д! = 4! для всех соответствующих 1 и у.
6) Объясните, почему результат упр. 63 является частным случаем (с). е) Докажите, что неравенство тапЬ(Т(т, и, з)) < г влечет тшйз (Т(ш, и, з) ш Т(1, г — и(пэ + з — 1), 1) ) < г + и. 1) Докажите, следовательно, что»! действительяо меньше, чем 1об М(п)/1об и для всех п > 1. 6) Обобщите (с) на случай, ко!да (А,В,С) — - реализация Ь только в слабом смысле упр. 61.
Ь) Из (б) следует, что гапЦТ(3, 1, 3) 4ЭТ(1, 4, 1)) < 10. Тогда из упр. 61, (б) также получим '1~Ь(Т(9,1,9) Е 2Т(3,4,3) 64 Т(1,16,1)) < 100, Докажите, что, если просто удалить строки А и В, соответствующие 16+ 16 переменным Т(1, 16, 1), можно получить реализацию Т(9, 1,9) Ю 2Т(3, 4,3), которая допускает улучшение.
Значит, фактически подучим тайЬ(Т(9,1,9) 92Т(3,4,3) !ЭТ(1,34,1)) < 100. !) Обобщив упр. 66, (с), покажите, что (!прпрзр)~1 < таей(® Т(тр, ир, зр)), р ! р 1 1) Докажите, следовательно, что 44 < 2.5. 68. (М45) Можно ли вычислить полинам лтл! к1зт + ' ' ' + к» !л» Е 164<!<» с меньшим, чем и-1, количеством умножений и 2и — 4 сложений? (Существует (") членов.) э 69. [НМ97) (В. Штрассен (Ъ'. Ятзаеееп), 1973.) Покажите, что определитель (31) матрицы размера и х и можно вычислить, произведя 0(иэ) умножений и О(п~) сложений или вычитаний, но не делений. (Указание. Рассмотрите бе!(1+ У), где У . Х вЂ” 1 ) ь 70. (НМйб) Харохпъерисптическиа полипом ух [3) матрицы Х определяется как!)ет (Лт — Х). Докажите, что «ели Х = (", ".
), где Х, и, и и У соответственно имеют размеры и х и, 1 х (и — 1), (и — 1) х 1 и (п — 1) х (и — Ц, то ио иУо нУ э У (Л) = У, (Л) ~Л- — — — — — — — ") . Лз Лз Покажите, что это отношение позволяет вычислить коэффициенты (л с приблизителыю -п умножениями, зи сложениями-вычитаниями и без делений. Указание.
Испатьзуйте ! 4 1 4 ~А В~ ~1 0)~А — ВВ'С В)( У 0) которое справедливо для любых матриц А, В, С и 0 размеров 1 х 1, 1 х гл, пз х 1 и т х гл соответственно, когда Р невырождена. и 71. (НМЗО) Цепочка отношений иолиномое подобна цепочке полиномов, но она допускает деление, как и сложение, вычитание н умножение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
