представлены в неоптимальном виде для краткости и простоты изложения; те читатели, которые реализуют данные алгоритмы, заметят, что многое можно ускорить. Например, окончательное значение Z2m-i(u)) на шаге N5 всегда равно нулю.

С1. [Критерий для простого случая.] Если и = 1, то присвоить

Zo <- хоУо + xiyi, zi <- (хо + xi){yo + yi) - zo

и завершить выполнение, иначе-присвоить m <- 2""". С2. [Переход к разностям.] Для О < к < т присвоить {хк,Хт+к) <- {хк + Хт+к,Хк -

Хт+к) и {ук,Угп+к) <г- (ук + Уш+к,Ук - Уш+к). (Получим х(и) Hiod (и"* - 1) =

ХО + • + Xm-iu""" и х(и) mod (и"* + 1) = Хт. + + Х2т-1и"*~; вычислим х{и)у{и) mod (и"* - 1) и х{и)у{и) mod (и"* + 1), а затем сгруппируем результаты согласно (59).)

СЗ. [Рекурсия.] Присвоить (го,..., Zm-i) циклической свертке (хо,..., Xm i) с (г/о,..., j/m-i). Присвоить также (г,..., Z2m-i) отрицательной циклической свертке (Xm,...,X2m-l) С (j/m , . . . , 2/2т-1).

С4. [Переход от разностей.] Для Q <к < т присвоить (г, Zm+k) <- {zk + Zm+k, Zk - Zm+k), тогда требуемый ответ- (го,..., Z2m-i)- I

N1. [Критерий для простого случая.] Если и = 1, присвоить t ч- хо(уо + yi), Zo <- t - (хо + xi)yi, Zi ч- t + (xi - хо)уо и закончить выполнение, иначе - присвоить m ч- 2-"2J и г ч- 2"\ (На следующих шагах используется 2" вспомогательных переменных Ху для О < г < 2т и О < j < г, представляющих

2т полиномов Xi{w) = Xio + Xnw Ч-----1- Xi(r i)u;". Аналогично используется

2""" вспомогательных переменных Уу.)

N2. [Инициализация вспомогательных полиномов.] Присвоить Xij ч- A(i+m)j <-Xmj+i, Yij Ч- y(i+m)j ч- j/mj+, для о < i < m и о < j < г. (Здесь получим х(и) = Ао(«") + mAi(m") -Ь • -Ь и"~Ат-1(и"); аналогичная формула имеет место для у{и). Наша стратегия - умножить эти полиномы по модулю (и""-1-1) = (и-" -1-1), выполнив операции по модулю (w"" -I- 1) с полиномами X(w) и Y{w) и на0дя их циклическую свертку длиной 2т, и тем самым получить с ее помощью

Х{и)у{и) ~ Zoiu") + uZl{u) + + u"-Z2m-l(un-)

N3. [Преобразовать.] (Сейчас, по существу, выполняется быстрое преобразование Фурье полиномов (Хо,...,Хт-1, О,... ,0) и (Уо,..., Ут-1,0,..., 0) с помощью tu"* в качестве (2т)-го корня единицы. Это эффективно, поскольку умножение на степень w не является реальным умножением.) Для j = [и/2] -1, ..., 1, О (в таком порядке) вычислить для всех m двоичных чисел s + t = (s[n/2j • «j+iO... 0)2 + {O...Otj-i ...to)2- Заменить (Xs+tiw),Xjf fjf 2j(w)) парой полиномов {Xs+t(w) + w(-/)=X, , i+2s(w), X,+t{w) - wi-/)X,+t+ii{w)), где s = 2-(sj+i ... sl„/2j)2. (Мы вычисляем 4.3.3-(39) с A" = 2m и w = tu/"; отметим замену двоичного разряда в «.) Точнее говоря, операция Xi{w) Ч- Xi{w) + wXi{w) означает присвоение Ху ч- Ху + Xjk) для к < j < г к Xij Ч- Ху - Х,у +г) для О < j < /с. Копирование Xi{w) можно выполнить без больших затрат памяти. Произвести такие же преобразования с Yk-

N4. [Рекурсия.] Для О < г < 2т присвоить {Zio,..., Zjfr-i)) отрицательную свертку (Хш,. . ,Xj(r i)) и (Уо,. . ,У(г-1))-

N5. [Обратное преобразование.] Для j = 0, 1, ..., [п/2\ (в таком порядке) присвоить

i(+tW + Z,+t+2iM, w-"{Z,+tiw) - Z,+,+,,(w)))

всем m, выбирая s и t, как на шаге N3.

N6. [Переупорядочение.] (Сейчас наша цель - завершить то, что сформулировано в конце шага N2, так как легко видеть, что преобразование Zk -это произведение преобразований Xk и Yi.) Присвоить z, Zio - Zrn+i){r-i) и Zmj+i Zij + 2(m+.)(j-i) для О < j < г и О < i < m,

Легко проверить, что в этих вычислениях для вспомогательных переменных необходимо максимум п дополнительных двоичных разрядов точности. Например, если jxi < М для О < г < 2" в начале алгоритма, то все переменные х и X всегда будут ограничены 2"М. Все переменные z и Z будут ограничены числом (2"М)2, где на п больше двоичных разрядов, чем требуется для окончательной свертки.

Алгоритм N выполняет А„ сложений-вычитаний, Dn делений пополам и Мп умножений, где Al = 5, Dl = О, Mi = 3; для n > 1 А„ = [п/2]2"+2 + 2L"/2J+iA-,/2i + (Ln/2J + l)2+42, On =2L/2J+iOrn/2i-b(Ln/2j+l)2+iHM,i =2L"/2J+iMr„/2V Решение имеет вид An = И 2"-i+ris"l - 3 2" + 6 25n, Dn = 4 2"-i+rig"1 - 2 2"-Ь 2 2"5n, Mn = 3.14-rig ni Здесь Sn удовлетворяет рекуррентной формуле Si =0, S„ - 25fn/2i + L"/2Ji и несложно доказать неравенство jnflgn] < 5n < 5n+i < nlgn -Ь n для всех n > 1. Алгоритм С выполняет примерно ту же работу, что и алгоритм N.

60. (а) В сумме Si, например, можно сгруппировать все члены, имеющие обшие значения j и к, в один трилинейный член; это даст трилинейных членов, когда {j.k) £ ЕхЕ, плюс и, когда (j, к) & ЕхО, и , когда (j, к) G ОхЕ. Когда J = /г, число -Xjj yjjZjj также без труда можно включить в Si. [Для случая, когда п = 10, метод умножения матриц размера 10 х 10 дает 710 некоммутативных умноже1Шй; это почти так же хорошо, как семь умножений матриц размера 5x5 методом Макарова (метод упоминается в ответе к упр. 12), хотя в схеме Винограда (35) используется только 600, когда допускается коммутативность. В подобной схеме Пан показал, что для начала М(п) < п * для всех больших п. Это пробудило большой интерес к проблеме (см. SICOMP 9 (1980), 321-342).]

(b) Пусть здесь 5 - это все индексы {i,j,k) одной задачи, а S-другой. [Когда т = п = S = 10, результат совершенно неожиданный: можно умножить две пары матриц размера 10 х 10, выполнив 1 300 некоммутативных умножений, в то время как схема для умножения каждой пары с 650 операциями неизвестна.]

61. (а) Заменить аа{и) величиной иаи{и). (Ь) Пусть ац{и) = Еаци и т. д. в реализации полинома длиной г = Ta.nkd{tijk)- Тогда tijk = J2a+v+,7=dEI=i4fbjiiCkii7-[Этот результат можно улучшить так: Ta.nk{tijk) < {2d + 1) x&nkd(tijk) в бесконечном поле, потому что трилинейная фор.ма Ец+,/+а=<г "С соответствует умножению полиномов по модулю и, как показали Бини и Пан (Bini and Pan, Csdcolo 17 (1980), 87-97).] (с, d) Это очевидно из реализаций упр. 48.

(е) Предположим, имеются реализации t и rt, такие, что YHi-ubjiCki = tijku 4-0{u+)яELlA(ii)LBjj,)LCkk)L=[i=jk]t,yku + 0{u+). Тогда

л г г г

Е EanA(,,,)i Y bjmBmj)LYl>"C(nk)L = Uj kti, j, k,u+ + 0{u++). L = l 1 = 1 m=l n = l

62. Ранг равен 3 согласно методу доказательства в теореме Wc Р = (" J). Грань ранга не может быть равна 1, так как нельзя получить ai(M)bi(M)ci(M) = а1(и)Ь2(и)с2(и) = и

и ai{u)b2{u)ci{u) = ai{u)bi{u)c2{u) = О по модулю и. Грань ранга равна 2, потому что реализации равны J), °), (J

Отметим, что грань ранга введена в работе Bini, Capovani, Lotti, and Romani, ЫогтШоп Processing Letters 8 (1979), 234-235.

63. (a) Пусть элементы T{m,n,s) и T{M,N,S) обозначены через i(i,j){j,k)(k,i) и T(i,ji)(jKi)(K,i) соответственно. Каждый элемент T(i,j)(jic){K,x) прямой суммы, где = (iJ), J = U,J) и К = (к, К) равен tij,j,k)(k.i)T(i,j>)(j,K)(K,i) по определению; значит, он равен [Т =1 и J = J и К = 1С].

(b) Примените упр. 61, (е) с M{N) = ranko(T(iV, iV, iV)).

(c) Имеем M{mns) < r, так как T{mns, mns, mns) = T(m, n, s)<S)T{n, s, m)®T(s, m, n). Если M(n) < R, TO M{n) < R для всех h, и, следовательно, M(N) < М(пГ1°8пЛГ1) < Rl°Sn ЛГ] < jij\[\osR/iogn [Этот результат появился в 1972 году в статье Пана.]

(d) Имеем Md{mns) < г* для некоторого d, где М<г(п) = гапк<г(Т(п,п,п)). Если Aid(n) < Д, то Mhd{n) < R для всех h и требуемая формула справедлива, так как Л/(п) < ["R согласно упр. 61, (Ь). В бесконечном поле остается множитель logiV. [Этот результат получен в 1979 году Вини (Bini) и Шёнхаге (Sclionhage).]

64. Имеем Е)с(Д(и) + E,jk 9j,k{u)) ~ y-Y.i<i,j,k<3iiyi*ki + 0(и*), где fk{u) = {xki + ихк2){у2к + иу\к)гкк+{хк1+ихкг)узк{{1+и)гкк-и{гк1 +Zk2+Zki))-Xki{y2k+yzk){zki +

Zk2 + Zkz) и gjk{u) = {Xkl + uxj2){y2k - Uyij){Zkj - UZjk) + (Xkl + uXj3){y2k + Uyij)Zkj.

[Лучшая верхняя грань, известная для rank(T(3,3, 3)), равна 23 (см. ответ к упр. 12). Грань ранга Г(2, 2, 2) остается неизвестной.]

65. Полином в указании имеет вид и EilLi H]=iixiyjZij + XijYijZ) + 0{и). Пусть Xij и Yij не определены для 1 < г < m и 1 < j < п. Присвоим также Xin = Ymj = О, Xmj = -YilTi Xij, Yin = -YjZiYj. Таким образом, с помощью тп + 1 умножений полиномов в области неопределенности можно вычислить Xij/j для каждого г и j, а также Е," 1 Е;=1 XijYij = Е,"7 XijYij. [SICOMP lO (1981), 434-455. В этой классической статье Шёнхаге среди прочих результатов получил результаты упр. 64, 66 и 67, (i).]

66. (а) Пусть ш = liminfn-too log Л/(n)/Iog п по лемме Т w > 2. Для всех б > О существует N с M{N) < Л+. Из доводов упр. 63, (с) следует, что log M(n)/log n < w + 2б для всех достаточно больших N.

(b) Это непосредственно следует из упр. 63, (d).

(c) Пусть г = гапкСЛ, q = (mns)", Q = (MNS)". Пусть задано е > О, тогда существует целая постоянная с, такая, что М(р) < ср" для всех положительных целых р. Для каждого целого h > О получим t = ()Т(т*М"*, niV"*, s*5~*) и rank(t) < г*". Пусть заданы кики пусть р = [(J)/("+)J. Тогда согласно упр. 63, (Ь)

rмk(T(pm=M-p7г=iV-ps5"=)) <rank(M(p)T(m=Л/- п"N-\sS-))

< гапк(с, {l)T{mM> n>N-\sS)) <c.r

и из п. (Ь) следует, что

p-gkQh-k {ртМ-pnN-psS-) < с<г\ Так как р > ЦУ""/2, получим

[DlQ"" < [\)*\2p)-qQ- <r"h-c.r\