AOP_Tom2 (1021737), страница 154
Текст из файла (страница 154)
Если я — любая вектор-строка, такая, что хА = О, то лА1е = О. Следовательно, все линейные зависимости в А появляются и в А1е н гвлк(А1е) < гаок(А). $ В качестве примера использования леммы Т рассмотрим проблему умножения полиномов. Предположим, необходимо умножить обычный полипом степени 2 на обычный полипом степени 3, вычисляя коэффициенты произведения: (ха+ х~ и+ ззи')(ро+ уги+ угии + узи') = ге+ гни+в,и +гзи +в4и + еви'. (54) 2 3 4 е Это сводится к проблеме вычисления шести билинейных форм, соответствующих тензору размера 3 х 4 х 6: ОООО 1000 0100 0010 0001 ОООО (55) Для краткости можно записать (54) в виде х(и)у(и) = х(и), где х(и) — полипом Ха + Хси+ Хги И т.
д. (34ы замкнули круг, вернувшись к началу данного раздела, но в отличие от (1), где полинам обозначается как и(х), мы обозначаем его как х(и); мы изменили обозначения, потому что сейчас нас интересуют переменные коэффициенты полинолюв.) Если каждую из шести матриц в (55) рассматривать как вектор размерности 12 с индексами (1,2), то ясно. что векторы линейно независимы, так как их нули занимают разные позиции. Следовательно,по лелсме Т ранг (55) равен по крайней мере шести.
Обратно, можно получить коэффициенты хо, гс, ..., 35 только с помощью шести цепочек умножений. Например, вычисляя (56) х(0)у(0), х(1)у(1), ..., х(5)у(5) при заданных значениях г(0), с(1), ..., х(5) я по интерполяционной формуле, приведенной выше, получим коэффициенты х(и). Вычисление х(1) и у(2) мо'кно выполнить всецело в терминах сложений и/или умножений параметров, и интерполяционная формула просто использует линейные комбинации этих значений. Таким образом, все цепочки умножений показаны в (56), а ранг (55) равен шести. (По существу, здесь используется та же техника, что и при умножении чисел с большой точностью в алгоритме 4.3.3Т.) Оказывается, реализация (Л, В, С) (55), набросок которой приведен в данном разделе выше, имеет вид о о 800 — 500 †7 1070 355 — 590 — 70 130 0 0 0 400 — 150 24 †7 305 — 50 4да †2 зб " 1го (57) — 120 55 — 10 120 — 274 225 — 85 15 7111 1 1 11 — 5 -1а 1о -5 Таким образом, схема действительно выполняет минимальное количество цепочек у.множений, но она совершенно непрактична, потому что включает в себя очень много операций сложения и умножения коэффициентов, Рассмотрим практический подход к построению более эффективных схем, предложенных Ш.
Виноградом. Во-первых, чтобы вычислить коэффициенты х(и)у(и), когда с1ей(х) = т и пей(у) = и, можно воспользоваться тождеством х(и)у(и) = (х(и) у(и) пюс1 р(и)) + х у„р(и), (58) где р(и) — -любой нормированный многочлен степени т + п. Полипом р(и) следует выбрать так, чтобы коэффициенты х(и)у(и) шос1р(и) легко вычислялись. Во-вторых, чтобы вычислить коэффициенты х(и)у(и) шос(р(и), когда полипом р(и) может быть множителем 0(и)г(и), где йсс1(0(и), г(и)) = 1, следует воспользо- ваться тождеством х(и)р(и) шос1 д(и)г(и) = (а(и)г(и)(х(и) р(и) гпос1 д(и)) + У(и)д(и)(х(и)р(и) шос)г(и))) пюс) у(и)г(и), (59) где а(и)г(и) + 5(и)д(и) = 1; это, по существу, применение к полиномам китайской теоремы об остатках.
В-третьих, всегда можно вычислять коэффициенты полинома х(и) р(и) шос1р(и), используя тривиальное тождество х(и)р(и) шоб р(и) = (х(и) спос1 р(и)) (р(и) шос1 р(и)) пюс1 р(и). (60) Повторно применив (58)-(60), можно, как будет показано ниже, получить эффективную схему. Например, для задачи (54) выберем р(и) = из — и и применим (58); основания для такого выбора р(и) будут приведены в дальнейшем. Если записать р(и) = и(и4 — 1),правило (59) приведет к х(и)р(и) шос1и(ис — 1) = ( †(ис — 1)хоро + и4(х(и)р(и) пюс1(и~ — 1))) шос1(из — и). (61, Здесь использован тот факт, что х(и) р(и) шос1 и = хоро., вообще, это хорошая идея —- выбрать р(и) так, чтобы р(0) = О, поэтому можно использовать данное упрощение. Если сейчас удастся определить коэффициенты во, вс, вг, вз полинома х(и) р(и) шос1 (ис — 1) = во + вс и + вгиз + созиз, то задача будет решена, поскольку и~(х(и)р(и) шос1 (и~ — 1)) пюб (и — и) = воис+ вси+ вгиг+ взи, и комбинация (58) и (61) приведет к х(и)р(и) = хоро+ (вс — хгрз)и+вги + взи + (во — хоро)и + хгрзи (62) (Конечно, эту формулу можно проверить непосредственно.) Остается решить проблему вычисления х(и)р(и) шос((ис — 1) (эта небольшая задача интересна сама по себе), На минутку допустим, что полинам х(и) имеет степень 3," а не 2.
Тогда коэффициенты х(и) р(и) пюс( (ис — 1) равны хоро + хсрз + хоро +хзрс хорс + хсро+ хгрз+ хзрю хорг+хгрс +хоро+ хзрз, хоуз+хсуг+хгрс +хоро и соответствующий тензор равен (! ~~!) (~! ~!И!!! ~) (~!!!) (65) Вообще, когда с1е8(х) = с1еб(р) = и — 1, коэффициенты х(и)р(и) пюс1(и" — 1) называют циклической сверткой (хо, хс,..., х„д) и (ро, рм..., р„с). сс-й коэффициент вь является билинейной формой 2„хсргз где сумма берется по всем с и у с с + 1 = — Й по модулю и. Циклическую свертку степени 4 можно получить, применив правило (59).
Первым шагом будет нахождение множителей ис — 1, т. е. (и — 1)(и+1)(из+1). Это можно записать в виде (иг — 1)(из+1), затем прилсенить правило (59) и снова использовать (59) по модулю (иг — 1) = (и — 1)(и+1). Однако легче обобщить китайскую теорему об остатках (59) непосредственно для нескольких взаимно простых множителей. Например, х(и)у(и) шойдс(и)дг(и)дз(и) = (ас(и)дг(и) дз(и) (х(и) у(и) спой дс(и)) + аг(и)дс(и)дз(и) (х(и) у(и) снос) дг(и)) + аз(и)дс(и)дг(и)(х(и)у(и) спой дз(и))) шойдс(и)дг(и)дз(и), (64) где а,(и)дг(и)дз(и)+аг(и)д,(и)дз(и)+аз(и)дс(и)дг(и) = 1. (Это соотношение можно также истолковать другим способом, заметив, что представление в виде частичных отношений 1/дс(и)дг(и)дз(и) равно ас(и)(дс(и) + аг(и)(дг(и) + аз(и)/дз(и) ) Из (64) получим х(и) у(и) шой (ис-1) = (с (из+ из+и+1) х(1) у(1) — с (из — из+и — 1) х( — 1) у( — 1) — с(иг — 1)(х(и) у(и) псой (из+1))) пюй (и — 1).
(65) Остается вычислить х(и) у(и) шой (из+ 1) и обратиться к правилу (60). Сначала преобразуем х(и) и у(и) пюс1 (иг+ 1) и получим Х(и) = (хз — хг)+ (хс — хз) и, У(и) = (уо — уг)+(ус — уз)и. Зателс по правилу (60) вычислим Х(и)У(и) = Ее+Лги+Лги'и, преобразовав его по модулю (из+1), получим (Яе — Яг) + Еси. Вычислить Х(и) У(и) несложно: можно воспользоваться правилом (58) с р(и) = и(и+ 1) и получить ~е = ХоУо, 3с = Хо1о — (Ле — Хс)(1о-1'с) + Хс1'» Яг = Хсу'с. (Тем самым мы заново открыли трюк 4.3.3-(2) более систематическим способом.) Объединив все вместе, получим следующую реализацию (А, В, С) степени 4 циклической свертки: 11011 11011 11222 (66) Здесь 1 обозначает — 1 и 2 обозначает — 2. Тензор для циклической свертки степени и удовлетворяет равенству (6 с) 1ьгл — сц-гСС нижние индексы рассматриваются но модулю и, поскольку й з — — 1 тогда и только тогда, когда с + г = lс по модулю п, поэтому, если (а,с), (бус), (см) — реализация циклической свертки, т.
е. (см), (Ь с), (аа); в частности, можно представить (63), преобразовав (66) в 11222 х — 11011 11011 (68) Сейчас все сложные скалярные величины оказались в матрице А. Это важно для практических целей, так как часто необходимо вычислить свертку для нескольких значений уе, ус, уг, уз, но с фиксированным набором хе, хс, хг, хз. В такой ситуации арифметика для х, может быть произведена для всех значений сразу и нет необходимости ее пересчитывать.
Таким образом, (68) приводит к следующей схеме вычисления циклической свертки юо, !81, и!2, и!з, где хо, х1, хг, хз заранее известны: 81 УО+У2, 82 — У1 +УЗ1 ВЗ = 81+82, 84 = 81 82~ У1~ 87 — 85 Вб~ П!2 = 4(ХΠ— Х1 + Х2 ХЗ) ' 84, 1 + Х! + Х2 — ХЗ) ' Вб, т5 = г (ХЗ Х1) ' 87,' 85 = УО У21 88 = УЗ т! 4(хо+х! 1 тз — 2 (хо +х1 — х2 хз) ' 1! — — т! + 7пг, +Хг+Хз) Вз, 85~ и!4 г ( ХО 1 Зг = и!8+ тб, 15 = 7п! — тг, 14 = т4 тб,' 482 = !1 — 72, из = !з — «. (69) и!о = !1 + гг, и!! = 15 + С4, Здесь 5 операций умножения и 15 — сложения, хотя определение циклической свертки включает в себя 16 умножений и 12 сложений.
Позже будет доказано„что необходимо 5 операций умножения. Возвратимся к нашей первоначальной проблеме умножения в (54). Воспользовавшись (62), получим реализацию 1000000 0111011 0011101 0011011 1011101 0100000 < 4011220'1 0011222) х —, 0411220 (70) В этой схеме используется на одну цепочку больше, чем минимальное число умножений в цепочке, но требуется намного меньше операций умножения параметров, чем (57). Конечно, это допустимо, так как схема все еще достаточно сложна: если нашей целью является простое вычисление коэффициентов го, 21,..., 25 произведения двух заданных полиномов (хо + х1и + хги )(уо + У!и + угиг + Узиз) как одноразовая задача, то лучше всего держать пари, что можно использовать очевидный метод с 12 умножениями и 6 сложениями, если, скажем, х! и уг — не матрицы. Другая уме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
