Мультипликативная сложность умножения в алгебрах

Алгоритмическое решение задач всегда было одним из основных предметов математики. В течение долгого времени такие решения были основаны на интуитивных соображениях. К началу XX в. много ярких примеров представили алгебра и теория чисел. Среди них — алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами. Эти и другие алгоритмические проблемы были решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале XX в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Одним из важнейших научных достижений в первой половине XX века стала точная математическая формализация понятий вычислимости и алгоритма.

В 1930;х годах был предложен ряд точных математических определений понятия алгоритма. Наиболее известные из них — машина Тьюринга, нормальный алгоритм Маркова, рекурсивные функции, А—исчисление Черча, машина Поста и другие. Все эти формализации алгоритма оказались эквивалентными с точки зрения алгоритмической разрешимости проблем. Последнее было обобщено в известном тезисе Черча о том, что формальное определение алгоритма эквивалентно его интуитивному пониманию.

В первую очередь эти понятия помогли установить алгоритмическую неразрешимость некоторых проблем, таких как, например, проблема останова, проблема пустоты и десятая проблема Гильберта. Поскольку понятие рекурсивной функции строгое, то с помощью математической логики можно доказать, что решающая некоторую задачу функция не является рекурсивной, что эквивалентно отсутствию для данной задачи разрешающего алгоритма. Аналогично, несуществование разрешающей машины Тьюринга для некоторой задачи равносильно отсутствию для нее разрешающего алгоритма.

Во-вторых, такие модели, как машина Тьюринга и рекурсивные функции, существенно повлияли на возникновение и развитие языков программирования. Еще в середине 50-х годов вычислительные машины получили широкое распространение в университетах и научно-исследовательских институтах, и тогда же наступило время стремительного прогресса в области программирования. Языки программирования стали удобным инструментом программирования при решении возникающих теоретических и прикладных задач.

С развитием компьютеров большую важность приобрел вопрос эффективности вычислений. В то время как для ряда практически важных и теоретически интересных проблем удалось найти эффективные решающие алгоритмы, некоторые задачи оказались достаточно трудны и быстрые алгоритмы для них до сих пор неизвестны. Это привело к возникновению и развитию теории сложности, занимающейся оценками количества ресурсов, необходимых алгоритму для решения задачи, таких как число шагов в той или иной модели вычислений (затрачиваемое время) или используемой в алгоритме памяти.

Первыми задачами этой теории стали задачи поиска эффективных вычислительных процедур для большинства практических задач, таких как арифметические операции над числами в позиционной системе счисления (в первую очередь, в двоичном представлении), алгоритмы линейной алгебры, операции с многочленами и многие другие. Практически сразу встал вопрос об эффективности ряда традиционных алгоритмов. К наиболее значимым следует отнести алгоритм умножения чисел в «столбик», имеющий квадратичную сложность (по длине входа) и алгоритм умножения матриц «строка на столбец», имеющий сложность 0(п3) для умножения квадратных матриц порядка п.

В 1962 году А. А. Карацуба предложил алгоритм умножения чисел длины п в позиционной системе счисления с битовой сложностью 0(nlog23^ (см. [49]). Таким образом, впервые было установлено, что традиционный алгоритм для умножения чисел не является оптимальным. Предложенный алгоритм использовал технику «разделяй и властвуй» и неявно основывался на вычислении и последующей интерполяции многочлена второй степени по трем точкам. Более полно этот подход был использован A. JI. Тоомом в 1963 году, предложившим для любого? > 0 алгоритм умножения чисел длины п сложности 0(п1+£), основанный на алгоритме умножения многочленов степени п (см. [52]). В 1971 году этот результат был улучшен А. Шёнхаге и Ф. Штрассеном, предложившими алгоритмы сложности 0(п log п log log п) (см. [33]). Этот алгоритм оставался асимптотически самым быстрым на протяжении 26 лет и был улучшен недавно Мартином Фюрером, предложившим алгоритм сложности 0(пlogп 2°(los*n)) x (cm. [23]). Годом позже алгоритм той же сложности, но с использованием совершенно иного подхода представили индийские математики (см. [21]).

Данная работа выполнена в контексте алгебраической теории сложности — теории сложности алгебраических задач в алгебраической модели вычислений. В самом общем смысле под алгебраической задачей понимается задача вычисления семейства дробно-рациональных функций от набора переменных над каким-нибудь полем. Примерами алгебраических задач являются операции над многочленами, например, вычисление многочлена в заданной точке, умножение и деление многочленов, матричные вычисления, такие как умножение матриц, обращение матриц, решение систем линейных алгебраических уравнений, и многие другие.

Алгебраическая модель вычислений подразумевает некоторую пошаговую процедуру, вычисляющую на каждом шаге определенную алгебраическую величину (как.

1 Очень медленно растущая функция log* п определяется как минимальное натуральное число к правило, это одна из арифметических операций: сложение, вычитание, умножение и деление) как функцию от входных значений и уже вычисленных величин. Вычисление считается завершенным, если все требуемые величины вычислены на каких-то шагах процедуры. Первым приближением понятия сложности алгебраической проблемы является минимальное количество таких шагов, необходимое для вычисления всех требуемых величин. Примерами алгебраических алгоритмов являются схема Горнера вычисления значения многочлена в точке, алгоритм Штрассена умножения матриц и многие другие.

Одной из центральных областей алгебраической теории сложности является сложность умножения в алгебрах. Алгеброй называется линейное пространство над некоторым полем, наделенное операцией умножения: отображением, которое двум произвольным элементам пространства ставит в соответствие определенный элемент этого пространства, причем это отображение является линейным по обоим аргументам. Задача сложности умножения в алгебре заключается в том, чтобы построить алгоритм, который для любых двух элементов алгебры вычислял бы их произведение, и имел бы наименьшую сложность. При этом под сложностью алгоритма могут подразумеваться различные понятия. Например, можно учитывать все арифметические операции над полем, которые требуются алгоритму для вычисления произведения в алгебре. Возникающая сложность называется арифметической (тотальной) сложностью. Другой способ определения сложности алгоритма — учитывать только так называемые существенные умножения, то есть такие операции умножения, оба операнда в которых зависят от входных переменных. В этом случае возникают понятия ранга и мультипликативной сложности умножения в алгебре (см. например, [14]).

Одной из наиболее важных и интересных задач в данной области является задача сложности умножения в алгебре матриц. В 1969 году Ф. Штрассен опубликовал алгоритм умножения квадратных матриц порядка п арифметической сложности 0(п1о&2 7)(см. [37]), тем самым впервые доказав, что традиционный алгоритм умножения матриц «строка на столбец» не является оптимальным2. После выхода статьи.

21с"2 7 и 2.807.

Штрассена эта задача привлекла большое внимание со стороны математиков из разных стран. Первое улучшение алгоритма Штрассена было получено в 1978 году В. Паном посредством анализа трилинейных форм (см. [31]). Через год группа итальянских математиков предложила новый метод для построения быстрых алгоритмов умножения матриц (метод приближенных разложений) и доказала с помощью него, что сложность умножения квадратных матриц порядка п не превосходит 0(п2−78°) (см. [3]). Затем в 1981 году в работе [34] Шёнхаге, обобщив идеи предшественников, получил новый метод для умножения матриц, который он назвал частичным матричным умножением. Этот метод позволил Шёнхаге понизить сложность умножения матриц до О (п260д). В той же работе при помощи другого нового метода (называемого методом прямых сумм) Шёнхаге доказал оценку 0(п2−522). Следующим шагом решения этой задачи был результат Копперсмита и Винограда, которые научились строить бесконечную последовательность алгоритмов, каждый последующий из которых дает оценку, лучшую, чем предыдущий. Они доказали, что сложность умножения матриц не превосходит 0(п2−496) (см. [19]). В 1986 году Штрассен, разработав совершенно новый подход (под названием метод относительных вычислений) к получению верхней оценки для умножения матриц, доказал оценку 0{п2Л79) (см. [34]). Через три года Копперсмит и Виноград, обобщив идеи Штрассена, построили алгоритм, затрачивающий 0(п2−376) арифметических операций, для умножения двух квадратных матриц порядка п (см. [20]). Оценка Копперсмита и Винограда оставалась наилучшей более 20 лет и была лишь немного понижена в недавних работах [36], [40] до 0(п2 373).

Нелинейные нижние оценки сложности умножения матриц отсутствуют. В 1999 году Блезер доказал, что ранг умножения матриц порядка п не меньше, чем |п2 — 3п (см. [4]). Амир Шпилька в 2001 году улучшил этот результат для конечных полей:

Зп2 — о (п2) для поля 2) и (§ + 2(р331))п2 — о (п2) для поля С. Р (р)(см. [35]). Совсем недавно Лэндсберг, основываясь на методах алгебраической геометрии, доказал новую нижнюю оценку Зп2 — 4п15 + п для умножения квадратных матриц порядка п над произвольным полем (см. [30]). Для малых значений п лучшей нижней оценкой на сегодняшний день является оценка 2п2 + п — 2 (п > 3), принадлежащая Блезеру (см. [9]). Существует гипотеза о том, что сложность умножения матриц порядка п равна о (п2+?) для любого е, однако до сих пор это утверждение не доказано и не опровергнуто (см. [43]).

В 2003 году Генри Коэи и Кристофер Уманс предложили новый подход для получения верхних оценок сложности умножения матриц, основанный на вложениях в групповые алгебры (см. [16]). Групповой называется алгебра, в которой существует базис такой, что множество элементов, входящих в этот базис, образуют группу относительно умножения в алгебре. Было показано, что, если сложность умножения в групповых алгебрах — почти линейна относительно размерности алгебры, то сложность умножения матриц порядка п — почти квадратична относительно п. В 2005 году этим подходом были получены первые алгоритмы умножения матриц сложности ниже, чем 0(п3) (см. [18]). Недавно авторы обобщили свой подход, научившись получать верхние оценки для умножения матриц посредством вложений в алгебры более общего вида, чем групповые алгебры (см. [17]). Несмотря на то, что все улучшения, полученные этим подходом, по сути представляют собой изложение классических результатов, переписанное на теоретико-групповом языке, это стимулировало рост интереса к групповым алгебрам.

В кандидатской диссертации А. Д. Поспелова (см. [51]) были исследованы коммутативные групповые алгебры над алгебраически замкнутыми полями и полем вещественных чисел. Им были установлены точные значения мультипликативной сложности умножения в таких групповых алгебрах. Этот результат является интересным потому, что любая нижняя оценка в алгебре над алгебраически замкнутым полем является универсальной, то есть она верна в алгебре над произвольным полем, алгебраическое замыкание которого совпадает с данным полем. В [32] А. Д. Поспелов обобщил некоторые результаты на случай некоммутативных групповых алгебр и доказал некоторые оценки, связывающие сложность умножения в групповых алгебрах и в алгебре матриц.

Целью данной диссертации является исследование сложности умножения в коммутативных групповых алгебрах над произвольными полями. Для решения этой задачи предложен метод нахождения структуры групповых алгебр, который позволяет использовать теорему Алдера-Штрассена для получения нижних оценок и теорему Блезера, описывающую все алгебры минимального ранга, для получения верхних оценок.

Другой целью диссертации является решение задачи определения алгебраической структуры алгебр минимальной мультипликативной сложности над произвольными полями. В 1981 году Алдер и Штрассен доказали свою фундаментальную нижнюю оценку для мультипликативной сложности умножения в произвольной ассоциативной алгебре с единицей (см. [1]). Так как мультипликативная сложность является обобщением понятия ранга, то оценка Алдера-Штрассена выполняется также для ранга умножения в алгебре. Практически сразу возникла задача описания алгебр минимального ранга с точки зрения их алгебраической структуры, то есть таких алгебр, для которых оценка Алдера-Штрассена выполняется как равенство для ранга. В течение почти 20 лет эта задача решалась многими математиками для различных классов алгебр над различными полями. Однако до 2002 года эта проблема оставалась открытой, пока Маркус Блезер не получил полное описание всех алгебр минимального ранга над произвольными полями (см. [10]). Так как доказывать нижние оценки для мультипликативной сложности обычно сложнее, чем для ранга, то в отличие от алгебр минимального ранга для алгебр минимальной мультипликативной сложности результатов было получено немного. Фейг получил описание специального класса алгебр — алгебр с делением минимальной мультипликативной сложности (см. [22]). Однако алгебраическая структура произвольных алгебр минимальной мультипликативной сложности была неизвестна. В частности, оставался открытым вопрос о существовании алгебры минимальной мультипликативной сложности, которая не является алгеброй минимального ранга. В данной диссертации доказано, что произвольная алгебра является алгеброй минимальной мультипликативной сложности тогда и только тогда, когда она является алгеброй минимального ранга, тем самым получено описание всех алгебр минимальной мультипликативной сложности с точки зрения их алгебраической структуры. Этот результат обобщает результат Блезера на случай мультипликативной сложности и результат Фейга на случай произвольных алгебр. Для решения этой задачи предложен новый метод доказательства нижних оценок для мультипликативной сложности умножения в алгебрах с ненулевым радикалом.

Краткое содержание диссертации.

Во введении содержится история вопроса, обосновывается актуальность темы исследования. В нём сформулирована цель диссертации, описана структура диссертации и перечислены основные результаты.

1. A. Alder, V. Strassen. On the algorithmic complexity of associative algebras. Theoret. Comput. Sei., 15:201−211, 1981.

2. Valery B. Alekseyev. On the Complexity of Some Algorithms of Matrix Multiplication. J. Algorithms, 6(l):71−85, 1985.

3. D. Bini, M. Capovani, F. Romani, and G. Lotti. 0(n2,7799) complexity for n x n approximate matrix multiplication. Inf. Process. Lett., 8(5):234—235, 1979.

4. Markus Blaser. A |n2 -lower bound for the rank of n x n-matrix multiplication over arbitrary fields. Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sei. (FOCS), 45−50, 1999.

5. Markus Blaser. Lower bounds for the multiplicative complexity of matrix multiplication. Comput. Complexity, 8:203−226, 1999.

6. Markus Blaser. Lower bounds for the bilinear complexity of associative algebras. Comput. Complexity, 9:73−112, 2000.

7. Markus Blaser. A 2.5n2-lower bound for the multiplicative complexity of n x n-matrix multiplication. In Proc. 18th Int. Symp. on Theoret. Aspects of Comput. Sei. (STACS), Lectures Notes in Comput. Sei. 2010, 99−110, 2001.

8. Markus Blaser. Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. Institut fur Theoretische Informatik, Germany.

9. Markus Blaser. On the complexity of the multiplication of matrices of small formats. J. Complexity, 19(1): 43−60, 2003.

10. Markus Blaser. A Complete Characterization of the Algebras of Minimal Bilinear Complexity. SIAM J. Comput., 34(2):277−298, 2004.

11. Markus Blaser, Bekhan Chokaev. Algebras of minimal multiplicative complexity. Proc. 27th Ann. IEEE Computational Complexity Conference (CCC), 224−234, 2012.

12. R. W. Brockett and D. Dobkin. On the optimal evaluation of a set of bilinear forms. Linear Algebra Appl. 19, 207−235, 1978.

13. Werner Buchi and Michael Clausen. On a class of primary algebras of minimal rank. Lin. Alg. Appl., 69:246−268, 1985.

14. P. Burgisser, M. Clausen, M. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.

15. D. Chudnovsky k, G. Chudnovsky Algebraic complexities and algebraic curves over finite fields, J. Complexity 4 (1988), p. 285−316.

16. H. Cohn, C. Umans. A Group-Theoretic Approach to Fast Matrix Multiplication. FOCS 2003: 438−449 (2003).

17. Henry Cohn, Christopher Umans. Fast matrix multiplication using coherent configurations, preprint, arXiv:1207.6528vl.

18. H. Cohn, R. D. Kleinberg, B. Szegedy, C. Umans. Group-theoretic Algorithms for Matrix Multiplication. FOCS 2005: 379−388 (2005).

19. D. Coppersmith and S. Winograd. On the asymptotic complexity of matrix multiplication. In Proc. SFCS, pages 82—90, 1981.

20. D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251−280 (1990).

21. Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication using Modular Arithmetic. Proceedings of the 40th annual ACM symposium on Theory of computing, p. 499−506, 2008.

22. Ephraim Feig. On systems of bilinear forms whose minimal division-free algorithms are all bilinear. J. Algorithms 2(3): 261−281, 1981.

23. M. Furer. Faster integer multiplication. Proceedings of STOC 2007, 57−66 (2007).

24. H. F. de Groote (1978). On the varieties of optimal algorithms for the computation of bilinear mappings: The isotropy group of a bilinear mapping. Theoret. Comput. Sci. 7, 1−24.

25. Hans F. de Groote. Characterization of division algebras of minimal rank and the structure of their algorithm varieties. SIAM J. Comput., 12:101−117, 1983.

26. Hans F. de Groote. Lectures on the Complexity of Bilinear Problems. Lecture Notes in Comput. Science 245. Springer, 1986.

27. Hans F. de Groote and Joos Heintz. Commutative algebras of minimal rank. Lin. Alg. Appl., 55:37−68, 1983.

28. Joos Heintz and Jacques Morgenstern. On associative algebras of minimal rank. In Proc. 2nd Applied Algebra and Error Correcting Codes Conf. (AAECC), Lecture Notes in Comput. Sci. 228, pages 1—24. Springer, 1986.

29. Joseph Ja’Ja'. On the complexity of bilinear forms with commutativity. SIAM J. Comput., 9:717−738, 1980.

30. J.M. Landsberg. New lower bounds for the rank of matrix multiplication, preprint, arXiv:1206.1530vl.

31. A. Schonhage und V. Strasscn. Schnelle Multiplikation grosser Zahlen. Computing, v. 7, pp. 281−292 (1971).

32. A. Schonhage. Partial and total matrix multiplication. SIAM J. Comput., 10(3) :434— 455, 1981.

33. A. Shpilka. Lower bounds for m, atrix product. In 42nd IEEE Symposium on Foundations of Computer Science, 2001.

34. A. Stothers. On the complexity of matrix multiplication. Ph.D. dissertation, University of Edinburgh, 2010.

35. V. Strassen. Gaussian elimination is not optimal. Numer. Math. 13, 354—356 (1969).

36. V. Strassen. Relative Bilinear Complexity and Matrix Multiplication. J. Reine Angew. Mathe. 375−376 (1987) pp. 406−443.

37. A. Waksman. On Winograd’s algorithm for inner products. IEEE Trans. Comp. C-19:360−361, 1970.

38. V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. Proceedings of the 44th ACM Symposium on Theory of Computing, 19−22 May 2012, New York, NY, Association for Computing Machinery, pp. 887—898.

39. S. Winograd. On multiplication in algebraic extension fields. Theoret. Comput. Sci., 8:359−377, 1979.

40. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987.

41. Алексеев В. Б. Сложность умножения матриц. Обзор. Киберн. сб. (1988) 25, 189−236.

42. Э. Берлекэмп. Алгебраическая теория кодирования. Перевод с английского Грушко И. И. Издательство «Мир», Москва, 1971.

43. М. Блезер, Чокаев Б. В. О почти билинейных алгоритмах для локальных и сверхосновных алгебр. Материалы XI Международного семинара «Дискретная математика и её приложения», с. 95−98. Изд-во мех.-мат. факультета МГУ, Москва, 2012.

44. JI. Ван дер Варден. Алгебра. М.: Наука, 1979.

45. Э. Б. Випберг. Курс алгебры. М.: Факториал-Пресс, 2002.

46. Дрозд Ю. А., Кириченко В. В. Конечномерные алгебры. Издательское объединение «Вища Школ», Киев, 1980.

47. А. А. Карацуба, Ю. П. Офман. Умножение многозначных чисел на автоматах. Докл. АН СССР, т. 145, № 2, с. 293−294 (1962).

48. Мельников О. В., Ремесленников В. Н., Романьков В. А., Скорняков JI. А., Ше-стаков И. П. Общая алгебра. Том 1. М.: Наука, 1990.

49. Поспелов А. Д. Сложность умножения в ассоциативных алгебрах. Диссертация. Московский государственный университет им. М. В. Ломоносова, 2008.

50. А. Л. Тоом. О сложности схемы из функциональных элементов, реализующей умножение целых чисел. Доклады Академии Наук СССР, т. 150, № 2, с. 496—498 (1963).

51. Чокаев Б. В. Исследование сложности умножения в коммутативных групповых алгебрах. Сборник тезисов лучших дипломных работ 2009 года, с. 105−106. Изд-во факультета ВМиК МГУ, Москва, 2009.

52. Чокаев Б. В. О сложности умножения в коммутативных групповых алгебрах. Труды VIII Международной Конференции «Дискретные модели в теории управляющих систем», с. 351−356. Изд-во Макс Пресс, Москва, 2009.

53. Чокаев Б. В. Исследование сложности умножения в коммутативных групповых алгебрах. Материалы X Международного семинара «Дискретная математика и её приложения», с. 150−153. Изд-во мех.-мат. факультета МГУ, Москва, 2010.