AOP_Tom2 (1021737), страница 158
Текст из файла (страница 158)
[Уховоннс. Рассмотрите произведение коэффициентов преобразования Фурье.] 58. (ВМ88) (а) Покажите, что любая реализация (А, В, С) тензора умножения полиномов (55) должна иметь следующие свойства: любая ненулевая линейная комбинация трех строк матрицы А должна быть вектором по крайней мере с четырьмя ненулевыми штеиентами и любая ненулевая комбинация четырех строк матрицы В должна иметь тю крайней мере три ненулевых элемента. (Ь) Найдите реализацию (.4,В,С) (55), которая испштьзует в качестве элементов только О, +1 и — 1, где г = 8. Попытайтесь использовать настолько много нолей, насколько это возможно. гь = хоУ»+ .
+ х»Уо — (к!э<У -! -Ь .. +х <У<,т!). Постройте эффективные алгоритмы для циклической и отрицательной циклической сверток для целых чисел, когда и,— степень 2. Ваш алгоритм полностью должен обходиться целыми числами, и дщтжно выполняться максимум 0(и!оби) умножений и максимум 0(п!об и)об1об и) сложений, вычитаний или делений четных чисел на 2. (Указание. Циклическая свертка порядка 2и может быть сведена к циклической н отрицательной циклической свертке порядка пч есчи воспользоваться (59) ] 60.
(М97) (В. Я. Пан.) Задача умножения матрицы размера (ти х и) на матрицу размера (п х в) соответствует тензору (1<;о 1<; ! !<ь, !) размера тии х ив х зтп. где 1<, зц< ь !<тщ ! = 1 тогда и только тогда, когда !' = т, уч = ! и 6~ = 6. Ранг этого тензора Т(щ, и, в) равен наименьшему числу г, такому, что числа а<т <, 6„! <, сы ! существуют и удовлетворяют соотношению х„Утес!, = ) ( ~ а„,хц ) ( ~ 6ть <У ! ) ( ) сьг<з„г). т<<<. ! «,, ! <!' < !<ь< ° !« ' ! <!<о ! <ь'<. !« ю !<!< !баб Пусть М(и) — ранг тензора Т(и, п, и).
Назначение упражнения- — использовать симметрию такого трилинейного представления для эффективного вычисления реализации умножения матриц, элементы которых — целые числа, когда щ = и = з = 2тт Для удобства разделим индексы (1,..., и) надва подмножества О = (1. 3,, и — 1) и Е = (2,4,, и) с и элементами в каждом и установим ваап»!но однозначное соответствие между подмножествами 0 и Е по правилу: ! = ! -Ь 1, если ! б О, ! = ! — 1, если ! б Е. Таким образом получаем ! = ! для всех индексов !.
а) Из тождества або + АВС = (и + А) (6+ В) (с + С) — (а -<- А) 6С вЂ” А(6+ В) с — аВ(с + С) следует, что х ! у,ьзы = ~ (хп + хо<Ну,ь + у т)(гм + гтк) — Е! — Тз — Ез, т< .т,ь< <ьтл!ев где В = ЕхЕхЕ <г Ех ЕхО <г ЕхОхЕ О ОхЕхŠ— множество всех тройных индексов, включающих максимум один нечетный индекс; Е! — сумма всех членов нида (х, ч- х;т)У ьза для (!',у, Й) б е и Вг, ез — подобные суммы членов хы(У ь + УВ)зг„ херц[хм + гзв), Ясно, что Е имеет 4и = -и членов.
Покажите, что каждУю з ! з г из сумм»т, Вм Вз можно реализовать как сумму Зтт трилинейных членов, кроме того, если Зи тройных индексов вида (т, т, !), (т, т, !) и (1, т, !) не содержатся в Е, можно ь бй. (М46) (Г. Ж. Нусбаумер (Н 3. 14чзвЬачпзег), 1980 ) В раздече определено, что циклическая свертка двух последовательностей (хо, хт,, х !) и (уо, ут..., у ! !)- .это последовательность (го,ет,,г !), где гь = хорь+ + х<уо+ хек!у -т+ + х! <уь !.
диалогично определим отирицатиельиую циклическую свертку, но с модифицировать Ес, Ез и Ез таким способом, что тождество останется справедливым без добавления каких-нибудь новых трилинейиых членов. Оледовательно, ЛХ(л) < -и -1- -и — -и, когда и четное. ! 3 2 2 3 2 4 2 Ь) Используйте метод (а), чтобы показать, что две незавнснмме задачи умножения матриц размера т х и х в можно выполнить с тле+ то+ лв + вт некоммутативными умножениями. 61. (МЯС) Пусть (Гоь) — теизор над произвольным полем. Определим гапйв(гбь) как минимальное значение г, такое, что существует реализация вида ) в,с(и)Ь,с(н)гм(н) = Г, ьн + 0(й~ ), с-..! где а,с(а), Ь,с(и), сы(в) .— полиномы от н над полем.
Таким образом, гвзйе --обычный ранг тензора. Докажите, что а) гапйззс(Г, !) < гапйз(соь); Ь) гасй(сч!) < (, ) гап144(1„!); с) гапйз((сов) б (1'; !)) < гап1св(162) + гапке(!';22) в смысле упр. 48; 4) газй,! 3 ((Гс 2) ес (Г„!.)) < гапйв(го!) гапйв (!'„2); е) гапьззз ((й !) з (г'„ь)) < гапьв (г(гч!)), где г = гапьв(гсзь) и гт означает прямую сумму Т 63 . ГО Т г копий Т. 62. (МЯХ) Гранью ранга тензора (й 2), обозначенной через гапЬ(в,зв), называется щ1пв>егапйз(во!), где гапйз определен в упр.
61. Докажите, что тензор (е,) (е ') имеет ранг 3, но грань ранга 2 над каждым полем 63. (НМЗО] Пусть Т(гл, и. в) — тензор умноясеиия матрицы, как в уцр. 60, и пусть ЛХ(йс)— ранг Т(22', Лс, Лг). а) Покажите, что Т(т, и, в) 22 Т(М, М, Я) = Т(тЛ|, иЛ', 3З). Ь) Покажите, что гапЬз(Т(гисг', лЖ, вЛС)) < гапйз(М(Н)Т(т, и, в)) (см. упр. 61, (е)).
с) Если Т(сл,и, в) имеет ранг < с, покажите, что М(йс) = 0(Лс !"'""Ю) при Ас -+ оо, где ы(си, л, в, г) = 3 103 г/ 1об слив. 41) Если грань рангатензораТ(пз, п, в) < г, покажите, что ЛХ(ЛГ) = О(М !мл" н1(!об Н) ). 64. [МЗО) (А.
Шенхаге (А ЯсЬопЬабе),) Покажите. что гапЬ2(Т(3,3,3)) < 21, так как М(М) = 0(М' ' ). и 65. (МЗ7) (А. Шенхаге,) Покажите, что гапйз(Т(т, 1, и) 0 Т(1, (ги — 1)(л — 1), 1)) = ти + 1. Указание. Рассмотрите трилинейную форму ) ~ (х, -1-иХ; )(и -1- нУс )(Я+ и в!) — (х! -4-. +х )(р! + 4-р )Е, =! з=! когда 2 ",ы! Хсз = 2 '," ! У„= О. 66. (НЛХЗЗ) Воспользуйтесь результатом упр. 65 для уточнения асимптотических граней из упр. 63. а) Докажите, что существует предел ас =!!щ„.44, !об М(и)/!об л. Ь) Докажите неравенство (тлв)"с < гап1с(Т(ги,и,в)). с) Пусть 1- — тензор Т(т,п.,в) ОЗ Т(ЛХ,Ас,Я).
Докажите, что (тлв)"~~ + (ЛХАсЯ)н~ < гапЬ(!). Указание. Рассмотрите прямое произведение г с самим собой. с1) докажите, следовательно, неравенство 16"~~ + Онс~ < 17 и получите, что ьс < 2.55. 6!. [НМ40[ (Д. Копперсмнт (П. СоррегзшйЬ) и Ш. Виноград,) Обобщая упр, 65 и 66, можно получить дагке лучшую верхнюю грань иг. а) Скажем, тензор (1! в) является иевмраждеииим, если гапй(сцгз1) = т, гапЬ(с!хай) = и и гапЬ(гз1ггз) = в в обозначениях леммы Т. Докажите, что тензор Т(т,п,в) для умножения матриц размера тп х пв является невырожденным. Ь) Покажите, что прямая сумма невырожденных тензоров является невырожденной. с) Тензор г размера т х и х з с реализацией (А, В, С) длиной г называется допускающим улучшение, если ои невырожден и существуют ненулевые элементы ф, ..., 4., такие, что 2 !" ! аибзгф = 0 для 1 < ! < т и 1 < 1 < и. Докажите, что в подобном случае грань ранга 1 6! Т(1, д, 1) < г, где д = !.
— гп — и. Указание. Существуют матрицы У и И' размера д х г, такие, что 2'; ! иоЬрд! = ) ',! ! аиш !д! = 0 и 2,! ! ипюггд! = д„ для всех соответствующих ! и ~. !)) Объясните, почему результат упр. 65 является частным случаем (с). е) Докажите, что неравенство гзпЬ(Т(т, и, в)) < г влечет гапЕг (Т(т, и, з) йг Т(1, г — п(т + в — 1), 1) ) < г + и. Г) Докажите, следовательно, что иг действительно меньше, чем !об М(п)/1об и для всех и, > 1. 6) Обобщите (с) на случай, когда (А,В!.С) — реализация 1, только в слабом смыгле упр. 61. Ь) Из (д) следует, что гапЬ(Т(3, 1, 3) !йТ(1, 4, 1) ) < 10, Тогда из упр. 61, (с)) также получим 'гапЬ(Т(9,1,9) йг 2Т(3,4,3) 1й Т(1, 16,1)) < 100. Докажите, что, если просто удалить строки А и В, соответствующие 16 + 16 переменным Т(1, 16, 1), можно получить реализацию Т(9,1,9) б!2Т(3,4,3), которая допускает улучшение.
Значит, фактически получим гапЬ(Т(9,1,9) й! 2Т(3,4,3) !и Т(1,34, 1)) < 100. !) Обобщив упр. 66, (с), покажите, что 'у(трпрвр) < гавдос(®Т(тр, пр, вр)) р=! р=! )) Докажите, следовательно, что аг < 2.5. 66. [М45[ Можно ли вычислить полинам х,к = кгхг+. +х„-гх„ Е !<!<!<в с меньшим, чем и — 1, количеством умножений и 2п — 4 сложенийу (Существует (") членов.) р 69. [НМв"г[ (В. Штрассен (Ъ'. Я!тавзен), 1973.) Покажите, что определитель (31) матрицы размера и х и можно вычислить, произведя 0(пз) умножений и 0(пз) сложений или вычитаний. но не делений. [Указание.
Рассмотрите бег(!' Ч- У), где У = Х вЂ” Ц ° ! О. [НМЯ5[ Хорвате рис!а ичесхий полинам ух(Л) матрицы Х определяется как с1ес (ЛХ вЂ” Х). Докажите, что если Л = („".), где Х, и, и и У соответственно имеют размеры и х п, 1 х (и. — 1), (и — 1) х 1 и (и — 1) х (и — 1), то ии иУр иУги Ух(Л) =У,(Л) (Л- — — — — — — —" ) Л Лг Л' Покажите, что это отношение позволяет вычислить коэффициенты ух с приблизительно ! и умножениями, -и сложениями-вычитаниями и без делений. Указание. Используйте з ! 4 (.4 В) (У 0) (А-ВВ-!С В) ( 1 О) которое справедливо для любых матриц А, В, С и 22 размеров 1 х 1, 1 х т, гл х 1 и гл х гл соответственно, когда Р невыраждена. ь 71. (НМ90) Цепочка ошношсний волвномое подобна цепочке полииомов, но она допускает деление, как н сложение, вычитание и умножение.
Докажите, что если /(хм, .., х„) мох«но вычислить цепочкой отно«пений полиномав, имеющей ш умножений в цепочке и З делений, то /(хм..., х ) и все и ее частные производные д/(хм..., с )/дх«для 1 < Й < и можно вычислить единственной цепочкой отношений полиномов, которая имеет максимум Згл+ л умножений в цепочке и 2«1 делений. (Например, любой эффективный метод вычисления определителя матрицы принодит к эффективному методу вычисления всех ее алгебраических дополнений, а значит, и к эффективному методу вычисления обратной матрицы.) Т2.
(М48) Можно лн определить ранг любого данного тензора (й «) над, скажем, полем рациональных чисел за конечное числа шагав? ТЗ. (НМЗ5) (Я. Х!оргенстерн (3. 21огбепз«егп), 197З.) Докажите, что любая цепочка полиномов для дискретного преобразования Фурье (37) имеет по крайней мере ! Зп««... щ„~б т«...
т сложений-вычитаний, если не существует умножений в цепочке и если каждый параметр умножения является комплексной постоянной с ~о, ( < 1. Указание. Рассмотрите матрицы линейных преобразований, вычисленных за первые Й шагов. 74. (НМ55) (А. Новаки (А. Хокай), 1978.) Большая часть теории, посвященной вычислению полиномов, касается умноясення в цепочке, однако умножение нецелочисленных постоянных также может быть весьма важным.
Назначение этого упражнении — развить соответствуюгцую теорию. Скажем, что векторы щ,..,,о, действительных чисел Я-зависимы, если сун«ествуют целые числа ()см.,., Й,), такие, что Зс«1(Йм,,Й,) = 1 и Й~щ + т )чо, — полностью целочисленный вектор. Если не существует таких целых чисел (Йм ..,, Й,), то векторы см .,., щ называются с-незавосвмммн. а) Докажите, что если столбцы матрицы У размера г х э Я-независимы, то существуют столбцы матрицы 1~(?, где П вЂ” любая упимолулярная матрица размера «х «(матрица из целых чисел с определителем, равным х1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
