Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 46
Текст из файла (страница 46)
очевидно, она не может иметь ранг, больший, чем г. К тому же согласно (51) матрица (Г;Озб) равна АЩ где Я— матрица размера г х пв вида ф~ ь~ = 6 ~ см. Если я — любая вектор-строка, такая, что яА = О, то лАО = О. Следовательно, все линейные зависимости в А появляются и в АЯ и гапк(АЯ) < гапк(А). В качестве примера использования леммы Т рассмотрим проблему умножения полиномов.
Предположим, необходимо умножить обычный полипом степени 2 на обычный полипом степени 3, вычисляя коэффициенты произведения: (ве + в1и + хзи )(де + ц1и + взи + дзи ) =ге+е1и+язи +язв +г1и +ези'. (54) Это сводится к проблеме вычисления шести билинейных фарм, соответствующих тензару размера 3 х 4 х б; 0000 1000 0100 0010 0001 0000 (50) Лля краткости можно записать (54) в виде х(и)у(и) = 3(и), где х(и) — полинам хе+ хги+ хзиз и т.
д. (Мы замкнули круг, вернувшись к началу данного раздела, но в отличие от (1), где папином обозначается как и(х), мы обозначаем его как х(и); мы изменили обозначения, потому что сейчас нас интересуют переменные коэгггфициеитм палнномов.) Если каждую из шести матриц в (55) рассматривать как вектор размерности 12 с индексами (г,у), то ясно, что векторы линейно независимы, так как их кули занимают разггые позиции. следовательно, по лемме т ранг (05) равен по крайней мере шести, Обратна, можно получить коэффициенты 30, 31, ..., 35 только с помощью шести цепочек умноженлй.
Например, вычисляя (5б) х(0)у(0), х(1)у(1), ..., х(5)у(5) г20 о О О < 1 1 1 1 1 1 -274 600 -600 400 О 1 2 3 4 5 225 -770 1070 -760 О 1 4 9 16' 25 ' 0 1 4 9 16 25 ' -35 355 -590 490 0162764 125| Гз -70 1ЗО -ЩО о о -150 24 305 -50 1 (57) -205 35 120 " 55 — 10 -5 1 — ! 5 — 1О 10 Таким образом, схема действительно выполняет минимальное количество цепочек умножений, но она совершенно непрактична, потому что включает в себя очень много операций сложения и умножения коэффициентов, Рассмотрим практический подход к построению более эффективных схем, предложенных 1П.
Виноградом. Ва-первых, чтобы вычислить коэффициенты х(и)у(и), когда г(е8(х) = т и 668(у) = и, можно воспользоваться тождеством х(и)у(и) = <х(и)у(и) шабр(и)) + х у„р(и), (58) тле р(и) — любой нормированный многочлен степени т + и. Полинам р(и) следует выбрать так, чтобы коэффициенты х(и)у(и) шог( р(и) легко вычислялись. Во-вторых, чтобы вычислить коэффициенты х(и)у(и) шаг(р(и), когда папином р(и) может быть множителем д(и)г(и), где 8сг)<д(и), г(и)) = 1, следует воспользо- при заданных значениях х(0), 3(1),..., 3(5) и по интерполяцноннай формуле, приведенной выше, получим коэффициенты х(и).
Вычисление х(г) и у(у) можно выполнить всецело в терминах сложений и/или умножений параметров, и интерпаляционная формула просто использует линейные камбинапии этих значений. Таким образом, все цепочки умножений показаны в (50), а ранг (55) равен шести, (Па существу, здесь используется та же техника, что и при умножении чисел с большой точностью в алгоритме 4,З.ЗТ.) Оказывается, реализация (4,В,С) (50), набросок которой приведен в данном разделе выше, имеет вид ваться тождеством х(и)у(и) шоб 9(и)г(и) = (а(и)г(и)(х(и)у(и) пюц 4(и)) + Ь(и)д(и)(х(и)у(и) пюб г(и))) шод д(и)г(и), (59) где а(и)г(и) + Ь(и)д(и) = 1; это, по существу, применение к палиномам китайской теоремы об остатках.
В-третьих, всегда можно вычислять коэффициенты полинома х(и) у(и) пюбр(и), используя тривиальное тождество х(и)у(и) пюц р(и) = (х(и) шадр(и)) (у(и) пюа р(и)) люб р(и). (60) Повторно применив (58)-(60), можно, как будет показано ниже, получить эффективную схему, Например, для задачи (54) выберем р(и) = из — и и применим (58); основания для такого выбора р(и) будут приведены в дальнейшем. Если записать р(и) = и(и~ — Ц, правило (59) приведет к х(и)у(и) шоб и(и~ — Ц = (-(из — Цхоуо + и~(х(и) у(и) шос) (и~ — Ц)) пюс( (и — и). (61, Здесь использован тот факт, что х(и) у(и) пюс( и = хоуо, вообще, зто хорошая идея— выбрать р(и) так, чтобы р(0) = О, поэтому можно использовать данное упрощение.
Если сейчас удастся определить коэффициенты во, вы вз, вз полинома х(и)у(и) пюа (и~ — Ц = во + в1 и + взиз + взиз, то задача будет решена, поскольку 4(()()6(4Ц)~(з)4++2+3 и комбинация (58) и (6Ц приведет к х(и)у(и) = хоуо+ (вз — хзуз)и+ взи'+ изи'+ (во — хоуо)и +хзузй. (62) (Конечно, эту формулу можно проверить нецосредственно.) Остается решить проблему вычисления х(и)у(и) пюд(из — Ц (эта небольшая задача интересна сама по себе). На минутку допустим, что полинам х(и) имеет степень 3; а не 2, Тогда коэффициенты х(и)у(и) пюд (и~ — Ц равны хоуо + х1уз+ хзуз + хзум хауз + хоро+ хзуз+ хзую хауз + хзуз + хзуо + хзуз ~ хауз + хз уз + изу1 + хзуо и соответствующий тензор равен (~~!!) (! ~!) (!!! ~) (~!!!) (8) Вообще, когда бей(х) = бей(у) = и — 1, коэффициенты х(и)у(и) пюд (и"-Ц называют циклической сверткай (хо,хз,...,х„з) и (уо,уы ° ° уч-з) к-и козффю циент вз является билинейной формой ~,'х;ут, где сумма берется по всем з и з с 1+ з гн й па модулю и.
Пиклическую свертку степени 4 можно получить, применив правило (59). Первым шагом будет нахождение множителей из -1, т. е. (и-Ц(и+ Ц(из+ Ц, Это можно записать в виде (иг — Ц(из + Ц, затем применить правило (59) и снова использовать (59) по модулю (иг — Ц = (и — Ц(и+ Ц.
Однако легче обобщить китайскую теорему об остатках (59) непосредственно для нескольких взаимно простых множителей. Например, х(и) у(и) шод 91 (и) йг(и) дз(и) = (аг(и) йг(и)йз(и) (х(и)9(и) пюб йг(и)) + аг(и) й(и) йз(и) (х(и) 9(и) пкк( Чг(и)) + аз(и) чг(и) чг(и) (х(и) я(и) пюс$ чз(и))) шоб чг(и)чг(и) чз(и), (64) где аг(и)дг(и)йз(и)+аг(и)йг(и)дз(и)+аз(и)дг(и)дг(и) = 1.
(Это соотношение можно также истолковать другим способом, заметив, что представление в виде частичных отношений 1/йг(и)йг(и)дз(и) равно аг(и)/9г(и) + аг(и)/дг(и) + аз(и)/яз(и) ) Из (64) получим х(и)з(и) шоа (и — ц = (з(и +и +и+ цх(цй(1) 1(и -и +и-цх(-цУ(-1) Р г Ц( ( )„(и)шоб( г+Ц)) шоб(„4 Ц (65) Остается вычислить х(и) у(и) пюб (из + Ц и обратиться к правилу (60). Сначала преобразуем х(и) и р(и) шоб (из+ Ц и получим Х(и) = (хо-хг)+(хг — хз)и, У(и) = (уо-Фг)+ Ь1 — рз) и. Затем по правилу (60) вычислим Х(и)У(и) = Хо+Я1и+Ягиг и, преобразовав его по модулю (иг+ Ц, получим (Яо - Ег) + Уг и.
Вычислить Х(и) У'(и) несложно: можно воспользоваться правилом (58) с р(и) = и(и+ Ц и получить Ло = Хо1'о Хг = Хо1'о — (Хо-Хг)(Ъо-Ъ~) + Хг1'ы Яг = Хгуз. (Тем самым мы заново открыли трюк 4.3.3-(2) более систематическим способом.) Объединив все вместе, получим следующую реализацию (А, В, С) степени 4 цнкли- ч'ской свертки: 11011 11011 11222 (66) Здесь 1 обозначает -1 и 2 обозначает -2. Тензор для циклической свертки степени и удовлетворяет равенству (67) нижние индексы рассматриваются но модулю и, поскольку г,.з = 1 тогда и только тогда, когда г + г = Ь по модгглю и, поэтому, если (ая), (Ьд), (сы) — реализация циклической свертки, т. е.
(см), (Ь и), (ао); в частности, можно представить (63), преобразовав (66) в (68) 11220 4' 11101 ' 11101 Сейчас все сложные скалярные величины оказались в матрице А. Это важно для практических целей, так как часто необходимо вычислить свертку для нескольких значений йо, йг, уг, дз, но с фиксированным набором хо, хг, хг, хз. В такой ситуации арифметика для х может быть произведена для всех значений сразу и нет необходимости ее пересчитывать. Таким образом, (68) приводит к следующей схеме вычисления циклической свертки 488, 481, 482, 483, гДе хо, 81, ХЗ, хз Заранее известны: 81=УО+УЗ 82=У1+УЗ ЗЗ =81+82, 84 =81-ЗЬ Уо — Уь 88 = Уз — У1 82 = 83 — 88~ + Х2+ ХЗ) 83, ГПЗ = 4 (ХΠ— Х1 + Х2 — ХЗ) ' 84, 83 ЗП4 — 2 ( ХО + Х1 + ХЗ Хз) ' 88 4ПЗ 2 (ХЗ Х1) 82 1 1 32 = п13 + п131 43 = гп1 гп2~ 44 п14 газ~ п21 = 4(го+Х1 гпз = 2(хо+ Х1 — хз — хз) ' 31 = пз1+ тз, (69) 481 — 13 + 14г 482 — 41 42 483 23 34' Здесь 5 операций умножения и 15 — сложения, хотя определение циклической свертки включает в себя 16 умножений и 12 сложений.
Позже будет доказано, что необходимо 5 операций умножения. Возвратимся к нашей первоначальной проблеме умножения в (54). Воспользовавшись (62), получим реализацию 1000000 0111О11 0011101 0011011 1011101 0100000 1011101 0011011 ) '4' 0011101 0411220 0111011 (70) В этой схеме используется на одну цепочку больше, чем минимальное число умножений в цепочке, но требуется намного меньше операций умножения параметров, чем (57). Конечно, это допустимо, так как схема все еще достаточно сложна: если нашей целью является простое вычисление коэффициентов го, 31, ..., гз произведения двух заданных полиномов (хо + х1и + хзиз)(Уо + У1 и + Уз из + Узиз) как одноразовая задача, то лучше всего держать пари, что можно использовать очевидный метод с 12 умножениями и 6 сложениями, если„скажем, хз и уз — не матрицы. Другая умеренно привлекательная схема, требующая 8 умножений и 18 сложений, приведена в упр.
58, (Ь). Заметим, что если хь фиксированы, когда уз изменяются, то (70) производит вычисления с 7 операциями умножения и 17 операциями сложения. Хотя даже эта схема не особенно пригодна в том виде, в котором она построена, наш вывод иллюстрирует важную технику, полезную в различных ситуациях. Например, Виноград воспользовался этим подходом для вычисления преобразования Фурье с помощью значительно меньшего количества операций умножения, чем необходимо для алгоритма быстрого преобразования Фурье (см. упр. 53). В завершение этого раздела найдем точный ранг тензора размера и х 11 Х П, который соответствует умножению двух полиномов по модулю третьего: го + 81 и + ° ° + 8„1п" =(хо+81и+ "+хо 1и" )(Уо+У1и+ ° ° ° +Уь 1п" )шо4)р(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
