алгоритм эффективен на 0-1 полиномах. Петерсон (Paterson) и Стокмейер (Stockmeyer) предложили также другой алгоритм, который использует около \/2п умножений.)

См. SICOMP 2 (1973), 60-66, а также J. Е. Savage, SICOMP 3 (1974), 150-158; J. Ganz, SICOMP 24 (1995), 473-483. Аналогичные результаты относительно сложений приводятся в работах Borodin and Cook, SICOMP 5 (1976), 146-157; Rivest and Van de Wiele, Inf. Proc. Letters 8 (1979), 178-180.

43. Если ai = aj + ak-шаг в некоторой оптимальной цепочке сложений для п + 1, вычислим х = х-х* и Pi = pkX- + Pj, где pt = х~ + • + х + 1. Опустим окончательное вычисление х""*. Одно умножение экономится, как только ak = 1, в частности когда i = 1 (см. упр. 4.6.3-31 0 6=1).

44. Пусть I = [IgnJ, и предположим, что х, х, х*, х предварительно вычислены. Если и(х) - нормированный полином степени п = 2т + 1, то его можно записать как и(х) = (х""* + a)v{x) + w{x), где v{x) и w{x)-нормированные многочлены степени т. Здесь приведен метод для п = 2+ - 1 > 3, который требует дополнительно 2 - 1 операций умножения и 2+i + 2-i - 2 операций сложения. Если п = 2, то можно применить правило Горнера для уменьшения п на 1. И если т = 2 < п < 2+ - 1, можно записать и(х) = x"*w(x) + w{x), где V и w - нормированные полиномы степени и - m и m соответственно. Индукцией по I можно показать, что потребуется максимум п + I - 1 умножений и п сложений после предварительных вычислений. [См. S. Winograd, IBM Tech. Disclosure Bull. 13 (1970), 1133-1135.]

Замечание. Можно также вычислить и(х), выполнив п+0(у/п) операций умножения и п + O(vn) операций сложения, по таким же обоснованным правилам, если необходимо минимизировать число умножений и сложений. Характерный для данного класса полином

pjkmix) =((•• (((х"- + ао){х+ + ai)(x+ + 2)

+ 02) • ) (х= + fik-j) + Ok-j) ix + 0)

"охватывает" коэффициенты при степенях {j,j+k,j+k+{k-l),... ,j+k+{k-l)+- +(+1), т - к, т - к + I,..., т - j}, где

m = m+j + (j + l) + ... + /e = m+( + ) - ().

Сложив такие полиномы pikmiix), Pikmix), Pkkmix) для mj = (1) + (~2), получим произвольный нормированный полином степени к + к + 1. [В статье Rabin and Winograd, Comm. on Pure and Applied Math. 25 (1972), 433-458, §2, доказано, что конструкция с jn + 0(log n) умножениями и < (1 + e)n сложениями возможна для всех б > О, если п достаточно большое.]

45. Достаточно показать, что ранг {Tjk) не больше, чем ранг (tijk), так как можно получить (tijk) из {Tijk), преобразовав его таким же способом с р-\ G~\ Н-\ Если Ujk = ]Е(=1 uabjiCki, то немедленно следует, что

Tijk = Ei<,<riZe=i ..«.i)(E;=: G,,,b,-,)(E=i Нкк-Ск.

[Г. Ф. де Гроот (Н. F. de Groote) доказал, что все нормальные схемы, которые дают произведение матриц размера 2 х 2 в результате семи умножений в цепочке, эквивалентны в том Смысле, что их можно получить одну из другой, выполнив умножение на невырожденную матрицу, как в данном упражнении. В этом смысле алгоритм Штрассена (Strassen) единственный. См. Theor. Сотр. Sci. 7 (1978), 127-148.]

46. Согласно упр. 45 можно добавить любое кратное строке, столбцу или матрице к другой строке, столбцу- или матрице без изменения ранга; также можно умножить строку, столбец или матрицу на не равную нулю константу или транспонировать тензор. Всегда можно найти последовательность операций, которая приводит данный тензор размера 2x2x2 к одной из таких форм: ОО, ОС), OQ), ОС), OQl). По теореме W последний тензор имеет ранг 3 или 2 в зависимости от того, сколько неприводимых множителей имеет полином - ги - q (один или два) в интересующем нас поле (см. (74)).

47. Тензор размера m х п х s имеет mns степеней свободы. Согласно упр. 28 все тензоры размера m х и х s можно выразить в терминах (т + и + s)r элементов реализации {А,В,С), кроме случаев, когда (т + и + s)r > mns. С другой стороны, предположим, что т > п > S. Максимальный ранг матрицы размера m х и равен п. Таким образом, можно получить любой тензор за ns умножений в цепочке, получая отдельно каждую матрицу. [В упр. 46 показано, что такая нижняя грань для максимального ранга тензора не является наилучшей возможной гранью и верхней гранью. Томас Д Хоуэл (Thomas D. Howell, Ph. D. thesis, Cornell Univ., 1976) показал, что существуют тензоры, имеющие ранг > \mnsj{m + п + S - 2)] над комплексными числами.]

48. Если [А,В,С) и {А ,В ,С)-реализации {tijk) и {tijk) длиной гиг соответственно, то А" = А® А, В" = В@ В, С" = С®С я А" = Л ® Л, В" = В ® В, С" = С®С - реализации {t-jk) и {t1jk) длиной г + г к г г соответственно.

Замечание. Многие, естественно, предполагают, что rank((tij)t) © {tijk)) = Ta.nk{tijk) 4-rank((Jjj,), однако в упр. 60, (b) и 65 показано, что это выглядит менее правдоподобным, чем кажется.

49. Согласно лемме Т rank(tij)t) > rank(ti(jfc)). Обратно, если М - матрица ранга г, то ее можно преобразовать с помощью операций со строками и столбцами, найдя такие невырожденные матрицы F и G, что матрица FMG будет содержать все О, за исключением г диагональных элементов, равных 1 (см. алгоритм 4.6.2N). Следовательно, ранг тензора FMG < г и он такой же, как ранг тензора М согласно упр. 45.

50. Пусть г = (г, г"), где 1 < г < m и 1 < г" < п, тогда t(iiyi)jk = Vjiik- Очевидно, что rank(ti(jfc)) = тп, так как {ti(jk)) - матрица перестановок. По лемме L Tank{tijk) > тп. Обратно, так как {tijk) имеет всего тп ненулевых элементов, то, очевидно, ее ранг < тп. (Существует, следовательно, ненормальная схема, требующая менее тп явных умножений. Подобной анормальной схемы не существует [Comm. Pure and Appl. Math. 3 (1970), 165-179]. Ho может быть достигнута некоторая экономия, если такая же матрица используется с s > 1 различными вектор-столбцами, поскольку это эквивалент умножения матриц размера (п х s) и (т х п)).

51. (а) Sl = уо + 2/1, S2 = 2/0 - yv, mi = (хо 4- xi)si, ma = (хо - xi)s2; tuo = mi 4- ma, wi = mi - ma. (b) Здесь несколько промежуточных шагов, использующих методику из раздела: ((хо - ха) 4- (xi - ха)и){{уо - 2/2) 4- (2/1 - 2/2)и) mod (и -(- и 4-1) = ((хо - Х2)(г/о - Уг) -(х1 - Х2)(2/1 - 2/2)) 4- {{хо - Х2){уо - У2) - (х1 - хо)(2/1 - уо))и. Первая реализация -

/1 1 1 0\ 10 11

Viioi/

/11 i о\

10 11

Vl1 о 1/

/1 1 1 2\

112 1 412 11/

Вторая реализация -

/1 1 1 2\

112 1 412 11/

/1 1 10\ 10 11

VI101/

Окончательно алгоритм вычисляет si = j/o 4- 2/ь «2 = 2/о - «з = 2/2 - 2/0- *4 = 2/2 - 2/ь Si = Sl + 2/2; mi = (хо 4- Xl 4- Х2)«5, т2 = (хо 4- xi - 2х2)«2, тз = (хо - 2xi 4- X2)s3,

т4 = §(-2x0 + Xl + X2)s4; ti = mi + m2, ti = mi - m2, ta = mi + тз, wo = ti - тз, wi = tz + m4, W2 = ti - m4.

52. Пусть к = {к,к"), когда /с mod и = к и к modn" = к". Нужно вычислить wk,k") = J2x(i,i")yui,j"), где суммирование производится так, что г + j = к {по модулю п) и г" + j" = /с" (по модулю п"). Это можно сделать, применив алгоритм п к 2и векторам Xi и длиной п" и получив и векторов Wk- Каждое векторное сложение становится п" сложениями, каждое умножение параметров становится п" умножением параметров и каждое умножение в цепочке векторов заменяется циклической сверткой степени п". [Если в подалгоритмах используется минимальное число умножений в цепочке над рациональными числами, то в этом алгоритме используется на 2{п -d{n)){n" - d{n")) операций больше минимального числа, d{n) - число делителей п, что следует из упр. 4.6.2-32 и теоремы W.]

53. (а) Пусть п{к) = (р - 1)р~~ = >р{р~) для О < Jfc < е и п{к) - 1 для к > е. Представьте числа {1,..., т} в виде ар* (по модулю т), где 0<А;<еиО<г< п{к), и а - фиксированный первообразный элемент по модулю р. Например, когда m = 9, можно положить а = 2; значениями являются {2°3°, 2i3°, 2°3\ 23°, 2*3°, 21з\ 2*3°, 23°, 2°32}. Тогда /(аУ) = Ео<Ке Eo<j<n(o""("V), г-да 9{hiXl) =

Вычислим fiki - 12o<j<n(i)i°p) для о < г < п{к) и для каждых к и I. Это циклическая свертка степени п{к + I) значений

Xi = wp"" и ys= Eo<j<n(o[* + J = ° модулю п{к + I))] F{ap),

так как fiki равно Е ХтУа (суммирование по r + s = г(по модулю п{к + 1))). Преобразование Фурье получается посредством суммирования соответствующих fiki- [Замечание. Когда образованы линейные комбинации Xi, как, например, в (69), результат будет чисто действительным или чисто мнимым, если циклическая свертка сконструирована по правилу (59) с uW-l = (и"<=/-1)(и"<>/ + 1). Это связано с тем, что операция по модулю (и"*"/-!) дает полином с действительными коэффициентами ш- , тогда как операция по модулю (n(fc)/2 2 gg полином с мнимыми коэффициентами -

Когда р = 2, применяют подобную конструкцию, используя представление (-1)а2* (по модулю т), где 0<fc<e, 0<г< min(e - к,1) и О < j < 2~*~. В таком случае используется конструкция упр. 52 с и = 2 и и" = 2*"*"; среди этих чисел не существует взаимно простых чисел; конструкция дает требуемое прямое произведение циклической свертки.

(Ь) Пусть ат +а"т" = 1 и пусть ш - w°""*", ш" = w°"*. Определим s = s mod m, s" = smodm", t = «modm, t" = «modm" таким образом, что = (w)")""-Отсюда следует, что f{s,s") = EtloE"lo()(w")""-P(«-«") Другими словами, одномерное преобразование Фурье т элементов - это фактически несколько измененное двумерное преобразование Фурье т х т" элементов.

Мы будем рассматривать "нормальные" алгоритмы, состоящие из: (i) сумм s, от F{k) и s{j), (ii) произведений mj, каждое из которых получается путем умножения одного из F{k) или S{j) на действительное или мнимое число Oj, (iii) дополнительных сумм tk, каждая из которых образуется из mk или tj (а не F{k) или s{j)). Окончательными значениями должны быть mk или tj. Например, "нормальная" схема преобразования Фурье для m = 5, построенная по (69) и по методу из п. (а), имеет следующий вид: S1 = F(l)+F(4), S2 = F(3)+F(2), S3 = S1+S2, S4 = S1-S2, ss = F(l)-F(4), se = F(2)-F(3), S7 = S5-S6; mi = i(w+w+w+w*)s3, m2 = \{ш-ш+ш*-ш)з4, тз = (w+w-w-w*)s5, m4 = 5(-w +ш +Ш* - w*)s6, ms = 5(01* - i)s7, me = 1 • F(5), mj = 1 S3; to = mi + me, tl = to + m2, t2 = тз + ms, <з = to - m2, <4 = m4 - ms, ts = ti + *2, te = <з + t4, t? = ti - t2, ts - t3 - t4, tg = me + тт. Отметим умножения на единицу в те и тт. Ясно, что реально