AOP_Tom2 (1021737), страница 222
Текст из файла (страница 222)
Эти наблюдения, приведенные в рабатах В.. 1т'. Вгосйе!в апд П. ПоЬЬ!и, Ъ!певг А!ЗеЬга апс! !Щ Аррйсастлв 19 (1978), 207 — 235, теорема 14; Ьешре! апб Ът'!побгвб, !ЕЕЕ Згапз. 1Т-23 (1977), 503-508; Ьешре), Зегопвьй апб 1Ч!побгас[, ТЬеогейса! Согпр. Яс!. 22 (1983), 285-296, можно использовать для зюлучення нетривиальных нижних граней рангов целочисленных матриц. Например, М. Р.
Браун (М. В Вгони) и Д. Добкин (П. БоЬв!и) (ХЕЕЕ Тгвлв. С-29 (1980), 337 — 340[ использовали это, чтобы показать, что реализации и х и умножений полнномов в целых числах должны иметь ранг > оп для всех достаточно больших и, когда о — любое действительное число, меньшее, чем число о ы = 3.52762680263240748061 54754081280751270182+; здесь пш„= 1/Н(э!и В, сох~ В), где Н(р,е) = р!8(1/р) + 4!8(1/е) — бинарная функция энтропии и В 1.34686 — корень уравнения сйп ( — х/4) = Н(е!и В, соя~ В). Реализация ранга 0(п !обо) для всех целых чисел, основанная на круговых полиномах, построена М. Камински (М.
Каш!пэЫ) [Х А!бопгйтэ 9 (1988), 137-147]. 10000000 10000111 11000100 ) 10000111 01000101 111ООО10 00100011 ' 10011111 00011001 00101000 00010000 Следующий экономный способ реализации умножения обычных полиномов степеней 2, 3 и 4 предложен Г. Кохеном и Л. К. Ленстра (Н. СоЬеп апб Л. К. Еепзсга, Маей. Сошр. 48 (1987), 81-82): < 100110 110100 010101 и 111010 001011 011001 001000 100000000 110010000 111001000 111111111 011100010 001100100 000100000 1000 1101 1110 1110 0000000000 ОООООООООО 1000000000 10011010110000 01010101101000 00101100011000 и 00000010110101 00000001101011 0110000100 0011100111 1011010010 0101001100 0000000111 1111 1100 0100 0000 00000000000010 В каждом случае матрицы А и В идентичны, 59.
[!ЕЕЕ 7гапз. АБЕР-28 (1980), 205-215.[ Заметим, что циклическая свертка является умножением полннома цо модулю и" — 1, а отрицательная циклическая саертка— умножением полинома по модулю и" + 1. Изменим запись, заменив и числом 2", и рассмотрим рекурсивные алгоритмы для циклической и отрицательной циклической сверток (сэ,...,тэ ~) последовательности (хо,...,хз -~) с (ре,...,рэ"-~). Алгоритмы представлены в неоптимальном виде для краткости и простоты изложения; те читатели, которые реализуют данные алгоритмы, заметят, что многое можно ускорить.
Например, окончательное значение Яе ~(п») на шаге К5 всегда равно нулю. С1. [Критерий для простого случая.) Если и = 1, то присвоить хо»- хоро+ х»у». х»» — (хе+ х»)(уо+ у~) — хе и завершить выполнение, иначе — присвоить нз» вЂ” 2" С2. [Переход к разностям.] Для О < Й < п» присвоить (хы х, » ь)»- (хь + х ьь, хь— х ~.ь) и (ужу„,чь)» — (уь + у чюуз — 9»-ь) (Получим х(и) шо»)(и — 1) = хо+. +х„, »и ' и х(п)шо»)(п +1) = х +.. +хз»иж '; вычислим х(п)9(и) шо»1 (и'" — 1) и х(п) р(п) шо») (и'" + 1), а затем сгруппируем результаты согласно (59).) СЗ. [Рекурсия.] Присвоить (хо,..., х„, ») циклической свертке (хо,, х, ») с (уа,..., у, »).
Присвоить также (х,..., хэ») отрицательной циклической свертке (х,„,...,хе ~) с (у,,...,уе»). С4. [Переход от разностей.] Для 0 < х < т присвоить (хь, х +ь)»- з(хь + х, ты хь— х ьь), тогда требуемый ответ — (хо,, хг -~). ! Х1. [Критерий для простого случая,] Если и = 1, присвоить 1»- хе(уо + р»), хо» вЂ” à — (хо + х»)дп х»»- 1+ (х» — ха)ро и закончить выполнение, иначе— присвоить т» — 2'ГЗ» и г»- 2""Ы». (На следующих шагах используется 24 Ы вспомогательных переменных Хб для 0 < 1 < 2т и 0 < 2 <», представляющих 2т полиномов Х,(ю) = Х,е+ Л»гю+. + Хц„пю" '. Аналогично игпользуется 2"т' вспомогательных переменных Уч.) Х2. [Инициализация вспомогательных полиномов.] Присвоить Хо» вЂ” Хбэ λ— х „;, У„»- УО»» — у,ь, для О < 1 < гп и О < 1 < г, (Здесь получим х(и) = Хо(к'") + иХ~(и ) + + и'"' 'Х»(п"); аналогичная формула имеет место для у(и).
Наша стратегия-- умножить эти полиномы по модулю (п~" + 1) = (к'-" + 1), выполнив операции по модулю (ю" + 1) с полиномами Х(ш) и У(ю) и найдя их циклическую свертку длиной 2гп, и тем самым получить с ее помощью х(и)у(п) = яо(п ) -». пя~(п ) + + иэ хз„, ~(п~).) » 13. [Преобразовать.] (Сейчас, по существу. выполняется быстрое преобразование Фурье патиномов (Хо,...,Х -ыО,.,.,О) и (Уе,,У,„пО,...,О) с помощью ю'~"' в качестве (2ш)-го корня единицы. Это эффективно, поскольку умножение на степень ю не является реальным умножением.) Для у = [и/2) — 1,..., 1, О (в таком порядке) вычислить для всех ш двоичных чисел э+ 1 = (в1„уз» ... э,»»0... О)е + (О .. 01,-»... Са)ь Заменить (Х,»»(п»),Х»,„.м(ю)) парой полиномов (Х,».,(ю) + шйз М Х„»,эсп(ю), Х,»»(ю) — ю<"Г~Н Х,юэп(ю)), где э' = 2'(э,»-~ ..
э1 рй)г. (Мь» вычисляем 4.3.3 — (39) с К = 2тп и ь» = за"/; отметим замену двоичного разряда в э'.) Точнее говоря, операция Х,(ш) +- Х,(ю) + п»~Х»(ю) означает пРисвоение Хч»»- Хч + ХЦ. Щ длк )с < У < г и Хч» — Хб — ХЦ»-ьч 1 дли О < у < а. Копирование Х»(ш) можно вьпюлнить без больших затрат памяти. Произвести такие же преобразования с У». Х4. [Рекурсия.] Для 0 < 1 < 2ш присвоить (Я*о,...,Я»р О) отрицательную свертку (Х,о,..., Хц„»») и (Уо,, Ур О).
1к15. [Обратное преобразование.[ Для ! =О, 1, ..., [и/2) (в таком порядке) присвоить (Я,эг(ш), Я,э! г,(ш)) +- 1(Я„(ш) + Я, ! г, (ги), ш !'г ! (Я,ег(ш) — Я,,, г, (ш))) всем пг, выбирая э и!, как на шаге к13. 1ч6. [Переупорядочение.[ (Сейчас наша цель--завершить то, что сформулировано в конце шага тЯ2, так как легко видеть, что преобразование Ег — это произведение преобразований Х!. и У,.) Присвоить э, ! — Я*о — 31 эц!, 0 и г гэ, з — У! + ЕО„.,!О Пд. 0<1< 0«оь Легко проверить, что в этих вычислениях для вспомогательных переменных необходимо максимум и дополнительных двоичных разрядов точности. Например, если [хг! < М для 0 < ! < 2" в начале алгоритма, то все переменные х и Х всегда бутут ограничены 2" М Все переменные г и Я будут ограничены числом (2" М)г, где на и больше двоичных разрядов,чем требуется для окончательной свертки.
Алгоритм 4 выполняет А сложений-вычитаний, .О делений пополам и М„ умножений, где А! = 5, .О! = О., М! = 3; для и > 1 А„= [и/2)2" + 2-"lг'эгА;„/г! + ([и/2)+1)2а+~ 52", 0 = 2!" гг!з г0!„ггг+([пг!2) +1)2"т~ и М„= 2!"1г!з гМ1 7г! Решение имеет вид А„= 11 2 -гэ1й 1 — 3. 2" + 6 2"Я„, Р„= 4 2 -гэ!гг ! — 2 2" + 2. 2" Я„, М„= 3 2" гэ1ггщ. Здесь Я„удовлетворяет рекуррентной формуле Я! = О, Я„= 2Я;„гг1+ [и/2), н несложно Доказать неРавенство 1п[!8 и) < Я„< Я„э! < гп(8 и + и дла всех и ) 1. Алгоритм С выполняет примерно ту же работу, что и алгоритм К. 60. (а) В сумме Бг, например, можно сгруппировать все члены, имеющие об!вне значения ! и Й, в один трилинейный член; зто даст и трилинейных членов, когда (дя) 8 ЕхЕ, г плюс мг, когда (1)г) 6 ЕхО, и иг, когда (! Ь) б ОхЕ.
Когда у = 1с, число — х зу„-гу также без труда можно включить в Е!. [Для с!!узах, когда п = 10! метод умножения матриц размера 10 х 10 дает 710 некомиутативных умножений; это почти так же хорошо, как семь умножений матриц размера 5 х 5 методом Макарова (метод упоминается в ответе к упр. 12), хотя в схеме Винограда (35) используется только 600. когда гопускается коммутативность. В подобной схеме Пан показал, что для начала М(п) < и для всех больших и. Это ге пробудило большой интерес к проблеме (см.
Я1СОМР 9 (1980), 321-342).] (Ь) Пусть здесь Я вЂ” это все индексы (г,з', й) одной задачи, а Я вЂ” дрзтой. [Когда т = и = э = 10, результат соверпгенно неожиданный: можно умножить две пары матриц размера 10 х 10, выполнив 1 ЗОО некоммутативных умножений, в то время как схема для умножения каждой пары с 650 операциями неизвестна.[ 61. (а) Заменить а,г(и) величиной иа,г(п). (Ь) Пусть а,г(н) = 2 а,геп" и т. д в Реализации полииома Длиной г = гап)са(епь).
ТогДа Ьо! = 2 „+ г ) '! ! аоеЬ,г„сы [Этот результат можно улучшить так! сап1г(гоь) < (2!1+ 1) гвп)сз(ее,гг) в бесконечном поле, потомУ что тРнлинейнаЯ фоРма 2 „э„э з а„б,с„соответствУет Умножению полиномов по модулю и~~', как показали Вини н Пал (Вггб авб Рап, Са1со1о 17 (1980), 87-97).[ (с, 8) Это очевидно из реализаций упр. 48, (е) Предположим, имеются реализации 1 и г1', такие, что 2„!" ! а,гЬ гсы = 1, !и~ + О(н~э ) и ~! АО! >сВ1 !!с!ьь гг, = [г= ! 5 й[1'...ь пж + О(изз!), тогда анАО, !с ) Ь, В<, !с )' сг С!„! гс — — 1чэе; ь и +О(и ).
Е !.!.!' ээю-!-! 62. Ранг равен 3 согласно методу доказательства в теореме %' с Р = (е '). Грань ранга не может быть равна 1, так как нельзя получить аг(и)Ьг(п)сг(и) = аг(и)Ьг(п)сг(п) с— э нз н ас(и)бг(и)сс(и) эз ос(и)5>(и)сг(и) си О по модулю ив+'. Грань рюсга равна 2, потому что реализации равны („' '], (", о), (' '). Отметим, что грань ранга введена в работе В>п<, Саротап<, Ьос<>, апс1 Потап<, улуоггпаз(оп Ргосевв(пд 7 есзегв 8 (1979), 234-235. 63.
(а) Пусть элементы Т(ги, и, в) и Т[Лз', Х, а) обозначены через <<,, >(>,» >(»„> и Т<> лцлк'><к > > соответственно. Каждый элемент Т<тд ><у »„- (>„- т > прямой суммы, где Т = ((,Х),,Т = (>',.7) и /С = (lс, К) равен ((с, >(,,» >(».в>Т«д ><лк >(к.» по определению; значит, он равен [Х' = Т и .7' = 7 и /С' = Х]. (Ь) Примените упр.
61, (е) с М(Х) = гап1са(Т(Х, Х, Х)). (с) Имеем М(тив) < г, так как Т(тив, тив, тив) = Т(т, ив)ЖТ(ив, т)<<ОТ(вт, и). Если М(и) < В, то М(и») < В» для всех Ь, и, следовательно, М(Х) < ЛХ(и(мз к!) < В<свв к> < ВХ<ск ядав [Этот результат появился в 1972 гаду в статье Пана.] (с1) Имеем Мв(гиив) < гз для некоторого Ы, где Мв(и) = гап1св(Т(и,и,и)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
