выполнять умножение здесь не нужно. Однако в силу принятых обозначений этот случай отмечается. Кроме того, он широко используется в рекурсивных конструкциях. Здесь те = /оо1, тг = /ою, *5 = /ооо + /ooi = /(2°), h = /юо + /loi = /(2) и т. д. Схему можно улучшить, включив sg = s3 + F(5), заменив mi выражением ((w + + w + w*) - l)s3 [что равно - 5з], a me--выражением 1 sg и удалив тг и tg. Это сокращает одно из тривиальных умножений на 1 и позволяет использовать данную схему для построения большей схемы. В улучшенной схеме /(5) = me, /(1) = ts, /(2) = <б, /(3) = ts, /(4) = tr-

Предположим, что есть нормальные одномерные схемы для т и т", использующие соответственно (а, а") комплексных сложений, {t,t") тривиальных умножений на ±1 или ±г и вообще {с ,с") комплексных умножений, включая тривиальные умножения. (Все нетривиальные комплексные умножения "простые", так как они включают только два действительных умножения и недействительных сложения.) Можно построить нормальную схему для двумерного (т х т")-случая, применив схему т к векторам F{t, *) длиной т". Каждый шаг Si превращается в т" сложений; каждое mj становится преобразованием Фурье т" элементов, но в этом алгоритме со всеми ак, умноженными на aj; каждое tk превращается в т" сложений. Таким образом, новый алгоритм имеет (ат" 4- с а") комплексных сложений, tt" обычных умножений и сс" комплексных умножений.

Используя эту технику. Виноград нашел нормальные одномерные схемы для малых значений m со следующими затратами {a,t,c).

т = 2 (2,2,2) т = 7 (36,1, 9)

m = 3 ( 6,1,3) т = 8 (26,6, 8)

т = 4 ( 8,4,4) т = 9 (46,1,12)

т = 5 (17,1,6) т = 16 (74,8,18)

Комбинируя эти схемы, как описано выше, получим методы, в которых используется меньше арифметических операций, чем в быстром преобразовании Фурье (БПФ), рассматриваемом в упр. 14. Например, когда m = 1008 = 7 • 9 16, затраты равны (17946, 8,1944). Таким образом можно осуществить преобразование Фурье 1 008 комплексных чисел с 3 872 действительными умножениями и 35 892 действительными сложениями. Улучшить метод Винограда можно, комбинируя взаимно простые модули и используя многомерные свертки, как показано в работе Nussbaumer and Quandalle, IBM J. Res. and Devei. 22 (1978), 134-144. Подход авторов позволяет сократить количество необходимых вычислений для комплексного преобразования Фурье 1 008 чисел до 3 084 действительных умножений и 34 668 действительных сложений. Для сравнения БПФ 1 024 комплексных чисел включает 14 344 действительных умножения и 27 652 действительных сложения. Однако, если используется улучшение подхода из ответа к упр. 14, для БПФ 1 024 комплексных чисел необходимо только 10 936 действительных умножений и 25 948 сложений, что совсем несложно выполнить. Поэтому тонкие методы быстрее работают только на машинах, которые значительно дольше умножают, чем складывают.

[См. Ргос. JVat. Acad. Sci. USA 73 (1976), 1005-1006; Math. Сотр. 32 (1978), 175-199; Advances in Math. 32 (1979), 83-117; IEEE Trans. ASSP-27 (1979), 169-181.]

54. max(2eideg(pi) - 1,..., 2e,deg(p,) - 1, ? 4- 1).

55. 2n - q, где ri -степень минимального полинома P (нормированного полинома р по крайней мере такой степени, что р{Р) - нулевая матрица) и q-число различных неразложимых множителей этого полинома. (Привести Р, выполнив подобные преобразования.)

56. Пусть tijk 4- tjik = Tijk + Tjik для всех г, j, к. Если (А,В,С)- реализация {tijk) рангаг, то Е[=1 c*i(Ei••OCEj bjiXj) - Ei.jikXiXj = Ei j ijiXiXj тя всех к. Обратно, пусть 1-е умножение в цепочке полиномов для 1 < / < г является произведением (q( 4- Ei Ot(Xi)(( 4- Ej Pjij), где ai и fit определяют возможные постоянные члены и/или нелинейные члены. Все члены степени 2, появляющиеся на любом шаге цепочки, могут

быть выражены в виде линейной комбинации [=1 iiXi)(Yj bjixj), поэтому цепочка определяет тензор (tijk) ранга < г, такой, что tjjk + tjik ~ Tijk + Tjifc- Это доказывает утверждение указания. Тогда гапк(гук + Tjik) - rank(«ij)c + tjik) < Ta,nk{tijk) + rank(tji)c) = 2rank(<ij*,).

Билинейная форма от xi, Xm, yi, Уп является квадратичной формой от m + и переменных, где Tijk = ti,j-m,fc для i < т и j > т; в остальных случаях Tijk = 0. Тогда rank(rij)c) + rank(rji*,) > ia.nk{tijk), поскольку мы получим реализацию (tijk), удалив последние п строк матрицы А и первые т строк матрицы В в реализации (А, В,С)

{тцк +Tjik).

57. Пусть N - наименьшая степень 2, превосходящая 2гг, и пусть u„+i = ••. = un-i = «„+1 = . . = vn-i = 0. Если Us = Ё;1оwut и V; = Etlдля 0 < s < iV, где Ш = f?"!, TO YJtZu ~*LJsVa = iVEMtiW«2, где последняя сумма берется по всем ti и <2 с О < ti,t2 < N, tl +t2 = t по модулю N. Если неравенства d < и и <2 < не выполняются, то члены сумм становятся нулями. Следовательно, <i+<2 < iV и сумма равна коэффициенту при г в произведении u{z)v{z). Если воспользоваться методом вычисления прямого и обратного преобразований Фурье из упр. 14, то количество комплексных операций будет равно 0{N log N) +0(N log Л) + 0{N) + 0{N log N) и N < 4n. [См. раздел 4.3.3C и статью Дж. М. Полларда (J. М. Pollard, Math. Сотр. 25 (1971), 365-374).]

При умножении полиномов с целыми коэффициентами можно использовать целое число ш, которое является порядком 2* по модулю простого числа р, и определять результаты по модулю достаточного количества простых чисел. Подходящие в этом отношении простые числа вместе с их наименьшими первообразными корнями г (для которых выберем ш = г(р-У modp, где pmod2 = 1) можно найти, как описано в разделе 4.5.4. Для t = 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), (И, 3), (19,11), (20,3), (29,3), (35,3), (55,19), (65,6), (95,3), (121,10). Для больших t все простые числа р вида 2q + 1, где q < 32, являются нечетными, и 2* < р < 2* заданы следующим образом: (р-1,г) = (11-2\3), (25-22°,3), (27-2°,5), (25-222,3), (27.222,7), {5-2\3), (7-22«,3), (27-22«,13), (152231), (17-223), (3-2*°,5), (13-228,3), (29-223), (23-228,5). Несколько последних простых чисел можно использовать с w = 2 для достаточно малых е. Такие простые числа обсуждаются в работах R. М. Robinson, Ргос. Атег. Math. Soc. 9 (1958), 673-681, и S. W. Golomb, Math. Сотр. 30 (1976), 657-663. Дополнительные ссылки на методы-для всех целых чисел можно найти в ответе к упр. 4.6-5.

Тем не менее метод из упр. 59 почти всегда предпочтительнее на практике.

58. (а) Вообще, если {А, В, С) реализует (tijk), то ((xi,..., Хт)А, В, С) является реализацией матрицы размера 1 х п х s, на пересечении строки j и столбца к которой находится Xitijk. В таком случае должно быть по крайней мере такое же множество ненулевых элементов в (xi,... ,Хт)А, каков ранг этой матрицы. Случаю, когда тензор имеет размер m X п X (т + п - 1), соответствует умножение полинома степени m - 1 на полином степени п - 1, соответствующая матрица имеет ранг п всякий раз, когда (xi,..., Хт) # (О,..., 0). Подобное утверждение имеет место при А В и т п.

Замечание. В частности, работая в поле из 2 элементов, говорят, что строки А по модулю 2 образуют "линейный код" т векторов, находящихся на расстоянии по крайней мере п, всякий раз, когда {А, В, С)-реализация, полностью состоящая из целых чисел. Эти наблюдения, приведенные в работах R. W. Brockett and D. Dobkin, Linear Algebra and its Applications 19 (1978), 207-235, теорема 14; Lempel and Winograd, IEEE Trans. IT-23 (1977), 503-508; Lempel, Seroussi, and Winograd, Theoretical Сотр. Sci. 22 (1983), 285-296, можно использовать для получения нетривиальных нижних граней рангов целочисленных матриц. Например, М. Р. Браун (М. R. Brown) и Д. Добкин (D. Dobkin) [IEEE Trans.

С-29 (1980), 337-340] использовали это, чтобы показать, что реализации пхп умножений полиномов в целых числах должны иметь ранг > an для всех достаточно больших п, когда а-любое действительное число, меньшее, чем число

Qmin = 3.52762 68026 32407 48061 54754 08128 07512 701824-;

здесь Qmin = l/H{sme,cose), где H(p,q) = plg(l/p) 4-glg(l/g)-бинарная функция энтропии и б W 1.34686 - корень уравнения sin{e - 7г/4) = H{sm e,cos в). Реализация ранга 0(п log п) для всех целых чисел, основанная на круговых полиномах, построена М. Камински (М. Kaminski) [J. Algorithms 9 (1988), 137-147].

/1 оооооооч

1 0 0 0 0 1 1 1\ (b) ( О 1 О О 1 1 О 1 .0 0 1 1 0 0 1 1/

/100001114 11000100 01000101) 11100010

ooloooiij looiiiii

0 0011001/ 00101000

vooo 1 оооо/

Следующий экономный способ реализации умножения обычных полиномов степеней 2, 3 и 4 предложен Г. Кохеном и А. К. Ленстра (Н. Cohen and А. К. Lenstra, Math. Сотр. 48 (1987), S1-S2):

/1 о о 1 1 0> 0 10 10 1 Vo о 1 о 1 1>

/1 о о о 1 1 о о Ц 0 10 0 10 0 11 0 0 10 0 110 1

Vq о о 1 о о 1 1 i

/1001101011000 On 01010101101000 00101100011000 00000010110101

Vo 000000110101 i/

/1 о о о о 0 110 10 0 1110 10 0 110 0 1

Vo о 1 о о о/

/1 0000000 0> 110 0 10 0 0 0 1110 0 10 0 0

111111111

0 1110 0 0 10

0 0 110 0 10 0 000100000 /1000000000000 0>

11010000000000

11101000000000

iiiooiiooooioo

11110011100111

iiooioiioiooio oloooioiooiloo oooooooooooiii Vq 000000000001 0

в каждом случай .матрицы А и В идентичны.

59. [IEEE Trans. ASSP-28 (1980), 205-215.] Заметим, что циклическая свертка является умножением полинома по модулю и" - 1, а отрицательная циклическая свертка- умножением полинома по модулю и" + 1. Изменим запись, заменив п числом 2", и рассмотрим рекурсивные алгоритмы для циклической и отрицательной циклической сверток (го,..., 22»-i) последовательности (хо,..., X2"-i) с (г/о,. •., 2/2"-i). Алгоритмы