AOP_Tom2 (1021737), страница 221
Текст из файла (страница 221)
(а) Пусть и(й) = (р — 1)р' » ' = »2(рс») для О < к < е и и(й) = 1 для 14 > е. Представьте числа (1,..., т) в виде аср" (по модулю т), где О < к < е и 0 < ! < и(к), и а — фиксированный первообразный элемент по модулю р'. Например, когда т = 9, можно положить а = 2; значениями являются (2о3о 243о 203! 2330 2330 233! 2433 233о 2о33) Тогда У(а'р ) = 2 „«,, 2 <щ! ывС"!'~'ОГ(аср~), где д(с,у,.й,() = а'ьвр»»!. Вычислим у,»! = 2 е«,„1! 2336!'"з!Г(авр') для О < 4 < и(к) и для каждых я и 1. Это циклическая свертка степени и(й -4- 1) значений З, =»44 3 »-»! н 9„= 2 „, [3+ 3 =0 (по модулю и(14+1))]Г(а'р!), так как 3',»с равно ~ х,дс (суммированне по г+ в = 3(по модулю и(к+1))). Преобразование Фурье получается посредством суммирования соответствующих у,»!.
[Замечасспе. Когда образованы линейные комбинации з„как, например, в (69), результат будет чисто действительным или чисто мнимым, если циклическая свертка сконструирована по правилу (59) с и"с" ~ — 1 = (пщ»!!2 — 1)(ищ~1~~+ 1). Это связюю с тем, что операция по модулю (и"~"13~ — 1) дает полинам с действительными коэффициентами »43+а! 3, тогда как операция по модулю (44"! Н + 1) дает полинам с мнимыми коэффициентами ы! — »4 Когда р = 2, применяют подобную конструкцию, используя представление ( — 1)'а'2» (по модулю т), где 0 < )с < е, 0 < 3 < ппп(е — к, 1) и 0 < у' < 2' » 2. В хаком случае используетсн конструкция упр.
52 с и' = 2 и и" = 2' ""2; среди этих чисел не существует взаимно простых чисел; конструкция дает требуемое прямое произведение циклической свертки. (Ъ) Пусть а'т'+авт" = 1 и пусть ы' = »44, ыв =»2' . Определим в' = 3!по»1т', вв = в той т", Г = 3 шоб т', 1в = 1щоб т" таким образом, чп! »44! = (ы')вч (ы")' ' . Отсюда следует, что у(в',вь) = 2„„' „2 ™„„(св')' '(ы )' ' Г(3',3в). Другими словами, одномерное преобразование Фурье т злементов — это фактически несколько измененное двумерное преобразование Фурье т' х тв элементов.
Мы будем рассматривать "нормальные" алгоритмы, состоящие из: (!) сумм в, от Г(/с) и во), (И) произведений сив, каждое нз которых получается путем умножения одного из Г(44) или З(у) на действительное или мнимое число п3, (ш) дополнительных сумм 1», каждая из которых образуется нз т» или 3! (а не Г()с) или в(!)). Окончательными значениями должны быть т» нли 3 . Например, "нормальная" схема преобразования Фурье для т = 5, построенная по (69) и по методу из п.
(а), имеет следующий вид: в! = Г(1)+Г(4), 32 = Г(3)+Г(2), 33 = 3~ 4-ви 34 = в — 33, 33 = Г(1) — Г(4), вв = Г(2) — Г(3), 37 33 вв' т! = 4 (»4+»4 4 »3 '4"! ! )33 т2 = 4 (»2 ы ! »4 ! ! )34 осв = 2 (34+»3 ь св )33 2 4 3 т4 = 2(-»3+»4 +и — 22 )вв, тв гв 3(»3 — »4 )вс, тв = 1 Г(5), сп! = 1 33; 3о = т! + тв, 2 4 3 ! 3 2 3! = 33+ тс, 12 = тв+ тв, 33 = 33 — тс, 14 = тс — тв, 13 = 3! + 32, 13 = 33 + 34, 32 = 3! — 32, 33 = 33 — 34, 32 = те + ти Отметим умножения на единицу в сив и спи Ясно, что реально выполнять умножение здесь не нужно. Однако в силу принятых обозначений этот случай отмечается Кроме того, он широко используется в рекурсивных конструкциях. Здесь тз = 1оом тт = 1о~о, гз = 1ооо + 1ооз = 1(2 ), ео = 1шо + 1шз = 1(2') и т.
д, Схему можно улучшить, включив вз = вз + Р(5), заменив поз выражением (1(ы + ш + ы + ы~) — 1) зз [что равно — зза], а тз — -выражением 1. зв и удалив тг и 1о. Это сокращает одно из тривиальных умножений на 1 и позволяет использовать данную схему для построения большей схемы. В улучшенной схеме 1(Ь) = то, 1(1) = Го, 1(2) = Го, 1(3) = Го, 1(4) = йа Предположим, что есть нормальные одномерные схемы для т' и то, использующие соответственно (а', ао) комгшексных сложений, (1',1о) тривиальных умножений на х1 илн Ы и вообще (с',с") комплексных умножений, включая тривиальные умножения.
(Все нетривиальные комплексные умножения опростые", так как они включают только два действительных умножения и недействительных сложения.) Можно настроить нормальную схему для двумерного (т х т )-случае, применив схему т к векторам Щ', *) длиной т". Каждый шаг з, пРевРащаетсЯ в то сложений; каждое тз становитсЯ пРеобРазованием Фурье то элементов, но в этом алгоритме со всеми пз, умноженными на аБ каждое 1о превращается в то сложений. Таким образом, новый алгоритм имеет (а'то + с'ао) комплексных сложений, Р1о обычных умножений и с св комплексных умножений.
Используя эту технику, Виноград нашел нормальные одномерные схемы для малых значений т со следующими затратами (о, й с). т = 2 ( 2, 2, 2) т = 3 ( 6, 1, 3) т=4 ( 8,4,4) т = 5 (17,1,6) Комбинируя эти схемы, как описано выше, получим методы, в которых используется меньше арифметических операций, чем в быстром преобразовании Фурье (БПФ), рассматриваемом в упр. 14. Например, когда т = 1008 = 7 9 16, затраты равны (17946,8.
1944). Таким образом можно осуществить преобразование Фурье 1 008 комплексных чисел с 3 872 действительными умножениями и 35 892 действительными сложениями. Улучшить метод Винограда можно, комбинируя взаимна простые модули и используя многомерные свертки, как показано в работе уйпззЪашпег апб Опапба1(е, 1ВМ Х Вез. алд Беое1. 22 (1978), 134 — 144. Подход авторов позволяет сократить количество необходимых вычислений для комплексного преобразования Фурье 1 008 чисел да 3 084 действительных умножений и 34 668 действительных сложений. Для сравнения БПФ 1 024 комплексных чисел включает 14344 действительных умножения и 27652 действительных сложения.
Однако, если используется улучшение подхода из ответа к упр. 14, для БПФ 1 024 комплексных чисел необходимо только 10 936 действительных умножений и 25 948 сложений, что совсем несложно выполнить. Поэтому тонкие методы быстрее работаю~ только на машинах, которые значительно долыпе умножают, чем складывают. [См. Ргос. 74аа Асаг1. ЯсЪ СЯА 73 (1976), 1005-1006; МаВь Сошр. 32 (1978), 175-199; Адоввсез ьа Магб, 82 (1979), 83 — 117; 1ЕЕЕ 21 зло. АБЕР-27 (1979), 169 181.) 54. шах(2езбеб(Рз) — 1,..., 2е,деб(Ро) — 1, д+ 1). 55. 2п' — д', где и'.— степень минимального пачннома Р (нормированного палинома р по крайней мере такой степени, что д(Р) — нулевая матрица) и 9' — число различных неразложимых множителей этого полинома.
(Привести Р, выполнив подобные преобразования.) 56. Пусть 1аз + бдз = т„з + гмо для всех з, 1, й. Если (А,В,С) — реализация (й з) ранга г, то),", сн(~, оох,)(х', бпхз) = 2', г ых,х> — — 2,',, гаох,х, для всех/с. Обратно, пусть 1-е умножение а цепочке полиномов для 1 < 1 < г является произведением (по+2,аох,)(4+2 Д~х,), где а~ и д~ определяют возможные постоянные члены и/или нелинейньзе члены. Все члены степени 2, появляющиеся на любом шаге цепочки, могут быть выражены в виде линейной комбинации 2,", с~ (2, оохз)(~ Ьдх!), поэтому цепочка ОПРЕДЕЛЯЕТ тЕНЗОР (!Ьл) РаНГа < Г, таКОй, Чта 1,,Л Ч- 1;,Л = Гчз + тзы Эта ДОКаЗЫВаЕт утверждение указания.
Тогда гапЦтчл + тем) = гапЦ!чв + !мл) < гапй(!пз) + гапв(!пв) = 2 гап)с(бо в) . Билинейная форма от х„, х, у,, у„является квадратичной формой от т+ и переменных, где т, л = ц „, в для з < т и ! > пц в остальных случаях тчв = О. Тогда гапЦгчв) + гапЦт„л) > гапк(йоз), поскольку мы получим реализацию (!Пл), удалив последние и строк матрицы А и первые т строк матрицы В в реализации (А, В, С) (тпв + т„л).
57. Пусть )з' — наименьшая степень 2, превосходящая 2и, и пусть и зл = .. = ия е +л = = оя л = О. Если У, = 2 ~ в'ими~ и 1; = 2 ',~ 'ммш для 0 < в < !в', где ы = вз '!~, то Я,' „'м "КК = Л'2 ипшз, где последняя сумма берется по всем !1 и !з с 0 < 6м !з < )у, В + !з = ! па модулю )л!. Если неравенства г1 < и и !з < и, не выполняются. то члены сумм становятся нулями, Следовательно, 1л+!з < Хи сумма равна коэффициенту при з' в произведении и[з)е(з). Если воспользоваться методом вычисления прямого и обратнога преобразований Фурье из упр.
14, то количество комплексных операций будет равно О(!у!об Ж) +О(Ж!об Х)+ О(Х)+ О(Х !об%) и )у < 4и. (См. раздел 4.З.ЗС и статью Дж. М. Полларда (Л. М. Ройвгг1, Маей. Сошр. 25 (1971), 365-374).) При умножении палиномов с целыми коэффициентами можно использовать целое число ш, которое является порядком 2' по модулю простого числа р, и определять результаты по модулю достаточного количества простых чисел.
Подходящие в этом отношении простые числа вместе с их наименьшими перваобразными корнями г (для которых выберем вз = гм-'Уз' щос[р, где р шо62' = 1) можно найти, как описано в разделе 4.5.4, для ! = 9 десятью наибольшими числами < 2зв являются р = 2зз — 512а+ 1, где (о,г) = (28, 7), (31, 10), (34, 13), [56, 3), (58, 10), (76,5), (80, 3), (85, 11), (91,5), (101, 3); десятью наибольшими числами < 2з' являются р = 2з' — 512о+ 1, где (о, г) = (1, 10), (11, 3), (19, 11), (20, 3), (29,3), (35,3), (55, 19), (бо,б), (95, 3), (121, 10). Для больших ! все простые числа р вида 2'6+ 1, где д < 32, являются нечетными, и 2ы < р < 2 заданы следующим зв образом: (р — 1,г) = (11 2з',3), (25 2'о 3), (27 2зо,5), (25 2™ 3) (27 2зз 7), (5. 2з' 3) 7 2зв 3) (27 2зв 13) (15 2зз 31) (17 2зт 3) (3 2зо 5) (13 2зв 3) (29 2зз 3) (23 2зв 5) Несколько последних простых чисел можно использовать с ы = 2' для достаточно малых е.
Такие простые числа обсуждаются в работах К. М. НоЬ!пвоп, Ргос. Атег. Маей. Яос. 9 (1958), 673-681, и 8. 1Ч. Со!ошЬ, Мазй. Сощр. ЗО (1976), 657-663. Дополнительные ссылки на методы.для всех целых чисел можно найти в ответе к уцр. 4.6 — 5. Тем не менее метод из упр. 59 почти всегда предпочтительнее на практике. 58. (а) Вообще, если (А, В, С) реализует (йбв), то ((хп.,., хм) А, В, С) является реализацией матрицы размера 1 х и х в, на пересечении строки у и столбца й которой находится х,хА~з.
В таком случае должно быть по крайней мере такое же множество ненулевых элементов в (хм..., хм) А, каков ранг этой матрицы. Случаю, когда тензор имеет размер т х и х (т+ и — 1), соответствует умножение полинома степени т — 1 на полинам степени и — 1, соответствующая матрица имеет ранг и всякий раз, когда (хп...,х ) ~ (О,...,0). Подобное утверждение имеет место при А вв В и тп вэ и. Замечание. В частности, работая в поле из 2 элементов, говорят, что строки А по модулю 2 образуют "линейный код" пл векторов, находящихся на расстоянии по крайней мере и, всякий раз, когда (А, В, С) — реализация, полностью состоящая из целых чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
