aj могут зависеть от заданных матрицы А и вектора В. Не важно, как выбраны А, В и значения aj; невозможно вычислить Р{х;ио, . ,Un), не выполнив п "умножений в цепочке".) Из предположения, что ранг матрицы А равен п + 1, вытекает, что т > п. [Указание. Покажите, что из любой такой схемы можно вывести другую схему, которая имеет меньше умножений в цепочке и п уменьшено на единицу.]

39. [М29] (Т. С. Моцкин, 1954.) Покажите, что схему вида

wi = х{х + ai) + Pi, Wk = Wk-iiwi+jkX+ ак)+5кХ +/Зк для 1 < к < т,

где ak, Pk -действительные числа Hjk,k -целые числа, можно использовать для вычисления всех нормированных полиномов степени 2т над полем действительных чисел. (Для различных полиномов можно по-разному выбирать а*,, /3, 7* и Sk-) Попытайтесь, когда возможно, предположить, что Sk = 0.

40. [М41 ] Можно ли нижнюю грань количества операций умножения в теореме С поднять от [n/2j -Ь 1 до Гп/21 -(- 1 (см. упр. 33)?

41. [22] Покажите, что действительную и мнимую части (а + Ы){с -Ь di) можно получить с помош;ью трех умножений и пяти сложений действительных чисел, где два сложения включают только а и Ь.

42. [36] (М. Патерсон (М. Paterson) и Л. Штокмейер (L. Stockmeyer).) (а) Докажите, что цепочка полиномов с m > 2 умножениями имеет максимум t -Ь 1 степеней свободы. (Ь) Покажите, что для всех п > 2 существуют такие полиномы степени п, все коэффициенты которых - нули или единицы, которые не могут быть вычислены любой цепочкой полиномов с менее чем [\/п\ умножениями, если все параметры aj должны быть целыми числами, (с) Покажите, что любой полином степени п с целыми коэффициентами можно вычислить при помощи полностью целочисленного алгоритма, который выполняет максимум 2 [\/п\ умножений, если количество произведенных сложений не имеет значения.

43. [22] Объясните, как вычислить х" -(- • • + ж -(- 1, выполнив 21{п + 1) - 2 операций умножения и /(п+ 1) сложения (не операций деления или вычитания), где 1{п) - функция, рассматриваемая в разделе 4.6.3.

► 44. [М25] Покажите, что любой нормированный полином и{х) = х" + u„-ix"~- -(-----1- мо

можно вычислить, выполнив n + 0{logn) умножений и < п сложений и использовав параметры ai, 02, - - -полиномы от Un-i, Un-2, ... с целыми коэффициентами. [Указание. Сначала рассмотрите случай, когда п = 2.]

► 45. [НМ22] Пусть (tijk)-тензор размера m х п х s и пусть F, G, Н - невырожденные матрицы соответственно размера mxm, пхпизхв. Если

= Е."=1 Е"=1 Efc=i Fi GjjHkktijk-

для всех i, j, к, докажите, что тензор (Tijk) имеет такой же ранг, как и {tijk). [Указание. Рассмотрите, что произойдет, когда F~, G~, применить таким же способом к {Tijk)]

46. [М28] Докажите, что все пары {zi,Z2) билинейных форм от {х\,Х2) и (2/1,2/2) можно вычислить с максимум тремя умножениями в цепочке. Другими словами, покажите, что каждый тензор размера 2x2x2 имеет ранг < 3.

47. [М25] Докажите, что для всех т, п и s существует тензор размера m х п х s, ранг которого равен по крайней мере [тпа/{т+п-\-а)\. Обратно, покажите, что каждый тензор размера m х п х s имеет ранг, не превышающий mns/max{m, п, s).

48. [М21] Если {tijk) и {tijk) -тензоры размера m х п х s и т х п х s соответственно, то их прямая сумма (tijk)9{tijk) = (tijk) является тензором размера {т+т) х {п+п) х {а+а), определенным как t-j, = tijk, если i < т, j < п, к < а, или как t-j = ti-m.j-n.fc-a,

если i > тп, j > п, к > s; в остальных случаях t/j = 0. Их прямое произведение {tijk){tijk) - (tijk) - это тензор размера mmxnnxss, определенный как tiii)jji)ky) = tijktiijiki Получите верхние грани rank(t"jj.) < rank(tijfc) + raak(tyj.) и xankitl-k) < Taak{tijk) •rank(t;-,fc).

► 49. [HM25] Покажите, что ранг тензора (Ujk) размера т х их 1 такой же, как его ранг, когда он записан в виде матрицы (Uji) размера тп х п, соответствующий традиционному определению ранга матрицы как максимального числа линейно независимых строк.

50. [НМ20] (Ш. Виноград.) Пусть {Ujk)-тензор размера тпп хпхт, соответствующий умножению матрицы размера m х п на вектор-столбец размерности п х 1. Докажите, что ранг тензора {tijk) равен тп.

51. [М24] (Ш. Виноград.) Придумайте алгоритм для циклической свертки степени 2, который использует 2 умножения и 4 сложения, не считая операций с ц. Подобно этому придумайте алгоритм для степени 3, используя 4 умножения и 11 сложений. (См. соотношение (69), которое позволяет решить аналогичную задачу для степени 4.)

52. [ЛГЙ5] (Ш. Виноград.) Пусть п = пп!, где п X п". Пусть заданы нормальные схемы для циклических сверток степени п и п", использующие соответственно {т,т") умножений в цепочке, {р,р") умножений параметров и {а,а") сложений. Покажите, как построить нормальную схему для циклической свертки степени п, используя тт" умножений в цепочке, рп" + тр" умножений параметров и ап" + та" сложений.

53. [НМ40] (Ш. Виноград.) Пусть w - m-й комплексный корень из единицы. Рассмотрим одномерное дискретное преобразование Фурье

f(s) = F{t)u\ для 1 < S < m.

a) Когда m = -степень нечетного простого числа, покажите, что эффективные нормальные схемы вычисления циклических сверток степеней (р- 1)р* для О < fc < е приводят к эффективным алгоритмам вычисления преобразования Фурье m комплексных чисел. Предложите подобную конструкцию для случая, когда р = 2.

b) Когда m = тт" и т X т", покажите, что алгоритмы преобразования Фурье для т и т" можно скомпоновать так, чтобы получить алгоритм преобразования Фурье для m элементов.

54. [ЛГЙ5] Теорема W доказана для бесконечных полей. Сколько элементов должно содержаться в конечном поле, чтобы доказательство теоремы W оставалось справедливым?

55. [НМ22] Определите ранг тензора (74), когда Р - произвольная матрица размера пхп.

56. [М32] (У. Штрассен (V. Strassen).) Покажите, что любая цепочка полиномов, которая вычисляет множество квадратичных форм Y- S37=i jkXiXk для 1 < fc < в, должна использовать, в целом, по крайней мере raak(r<jfc -Ьг,-,*,) умножений в цепочке. [Указание. Покажите, что минимальное число умножений в цепочке равно минимальному рангу (tijk), взятому по всем тензорам (tijk), таким, что tijk + tjik = Tijk Tjik для всех г, j, fc.] Воспользуйтесь этим для доказательства того, что любая цепочка полиномов, вычисляющая множество билинейных форм вида (47) и соответствующая тензору {tijk), нормален он или анормален, должна использовать хотя бы Tank{tijk) умножений в цепочке.

57. [ЛГЙО] Покажите, что быстрое преобразование Фурье можно использовать для вычисления коэффициентов произведения двух заданных полиномов степени п х{и)у{и), произведя O(nlogn) операций (точно) сложений и умножений комплексных чисел. [Указание. Рассмотрите произведение коэффициентов преобразования Фурье.]

58. [НМ28] (а) Покажите, что любая реализация {А, В, С) тензора умножения полиномов (55) должна иметь следующие свойства: любая ненулевая линейная комбинация трех строк матрицы А должна быть вектором по крайней мере с четырьмя ненулевыми элементами и любая ненулевая комбинация четырех строк матрицы В должна иметь по крайней мере три ненулевых элемента. (Ь) Найдите реализацию (А, В, С) (55), которая использует в качестве элементов только О, +1 и -1, где г = 8. Попытайтесь использовать настолько много нулей, насколько это возможно.

► 59. [М40] (Г. Ж. Нусбаумер (Н. J. Nussbaumer), 1980.) В разделе определено, что циклическая свертка двух последовательностей {xo,xi,.. .,x„-i) и {yo,yi,- ,yn-i) - это последовательность (20,21, ... ,2n-l), где Zk = ХоУк -I-----\-ХкУ0+Хк+1Уп-1 -\-----i-Xn-iyk + l-

Аналогично определим отрицательную циклическую свертку, но с

Zk = ХОУк -i-----\- ХкУО - {хк+1Уп-1 -I-----1- Xn-iyk + l)-

Постройте эффективные алгоритмы для циклической и отрицательной циклической сверток для целых чисел, когда п - степень 2. Ваш алгоритм полностью должен обходиться целыми числами, и должно выполняться максимум O(nlogn) умножений и максимум 0(п logn log logn) сложений, вычитаний или делений четных чисел на 2. [Указание. Циклическая свертка порядка 2п может быть сведена к циклической и отрицательной циклической свертке порядка п, есди воспользоваться (59).]

60. [М27] (В. Я. Пан.) Задача умножения матрицы размера (т х п) на матрицу размера (п X s) соответствует тензору it{i,j)(j,k}{k,i}) размера тп х ns х sm, где t{i,ji)(j,k){k,i) = 1 тогда и только тогда, когда г = г, f = j и к = к. Ранг этого тензора Т{т, п, s) равен наименьшему числу г, такому, что числа ау;, bjkn, Ckti существуют и удовлетворяют соотношению

XijyjkZk,= X] ( XT bjkiyjk( Cblfci-.

l<t<m !<<• l<i<m l<j<n l<k<s

l<j<n i<j<n l<k<s l<i<m

l<k<s

Пусть M{n) - ранг тензора Т{п, n, n). Назначение упражнения - использовать симметрию такого трилинейного представления для эффективного вычисления реализации умножения матриц, элементы которых - целые числа, когда m = п = s = 2г/. Для удобства разделим индексы {1,..., п} на два подмножества О = {1,3,... ,п - 1} и Е = {2,4,... ,п} с v элементами в каждом и установим взаимно однозначное соответствие между подмножествами О и Е по правилу: i = i + 1, если г G О, г = г - 1, если i G Е. Таким образом получаем г = i для всех индексов г.

а) Из тождества

обе + ABC = (а -Ь А)(6 + В){с + С)-{а + А)ЬС - А{Ь + В)с - аВ{с + С) следует, что

XijyjkZki= (хц + Xi)iyjk +y-,j)izki + Zjk) -Т,2 -Т,з,

1<г,],к<п (i.J,fc)€S

где S = ЕхЕхЕ U ЕхЕхО U ЕхОхЕ U ОхЕхЕ - множество всех тройных индексов, включающих максимум один нечетный индекс; Si-сумма всех членов вида {xij +Xki)yjkZjk для {i,j,k) G S и Е2, Ез -подобные суммы членов Xki{yjk +yij)zki, Xijyijizki + Zjn). Ясно, что S имеет 4г/ = членов. Покажите, что каждую из сумм Si, S2, S3 можно реализовать как сумму Зг/ трилинейных членов; кроме того, если Зг/ тройных индексов вида (г, г, г), (г, г, г) и (г, г, г) не содержатся в S, можно