Сложность умножения в ассоциативных алгебрах

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

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

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

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

Одной из центральных задач алгебраической теории сложности является сложность умножения в алгебрах. Для этого сначала определяется понятие алгебры и фиксируется класс изучаемых алгебр. Затем уточняется понятие алгоритма и его сложности.

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

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

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

В 1962 году А. А. Карацуба и Ю. П. Офман предложили алгоритм умножения чисел длины п в двоичной системе счисления со сложностью 0{v}°°2 3) (см. [25]). Этот алгоритм легко трансформируется в алгоритм умножения многочленов одного переменного степени п. Таким образом, впервые было установлено, что традиционный алгоритм не является оптимальным. Предложенный алгоритм использовал технику «разделяй-и-властвуй» и неявно основывался на вычислении и последующей интерполяции многочлена второй степени по трём точкам. Более полно этот подход был использован A. JL Тоомом в 1963 году, предложившим для любого е > 0 алгоритм умножения чисел длины п в двоичной системе счисления сложности 0(п1+е), основанный на алгоритме умножения многочленов степени п той же сложности (см. [29]). В 1971 году этот результат был улучшен А. Шёнхаге и Ф. Штрассеном, предложившими алгоритмы сложности 0(п log п log log п) для умножения многочленов степени п и чисел длины п в двоичной записи (см. [17]). Этот алгоритм оставался асимптотически самым быстрым на протяжении 26 лет и был улучшен совсем недавно Мартином Фюрером, предложившим алгоритм сложности п log п2°(ъ&*п) для умножения чисел (см. [10]).

Нетривиальные нижние оценки сложности умножения полиномов известны только в моделях с ограничениями. В общем случае из линейной независимости коэффициентов полинома-произведения следует лишь, что для умножения полиномов степени п требуется не менее 2п — 1 арифметических операций (см., например, [1, 5]). Большинство асимптотически быстрых алгоритмов основаны на дискретном преобразовании Фурье. В 1973 году Ж. Моргенштерн заметил, что дискретное преобразование Фурье имеет супер линейную сложность, а именно, Q (п log п), если в алгоритме трансформации использовать только коэффициенты, ограниченные некоторой константой (см. [13]). В 2004 году Петер Бюргиссер и Мартин Лотц обобщили эту оценку на произвольные алгоритмы умножения полиномов (см. [6]). Существует гипотеза о том, что в действительности сложность умножения многочленов равна 0(п log п), однако до сих пор это утверждение не доказано и не опровергнуто (см. [5]).

В 1969 году Ф. Штрассен опубликовал алгоритм умножения квадратных матриц порядка п сложности 0(тг10⁷) (см. [19]). Этот результат послужил отправной точкой развития алгебраической теории сложности. В течение 9 лет результат Штрассена оставался неулучшенным, однако в 1978 году В. Пан посредством анализа трилинейных форм предложил первую нетривиальную конструкцию для вычисления произведения матриц сложности, меньшей в третьем знаке после десятичной запятой, чем алгоритм Штрассена. После этого в течение 10 лет несколько групп учёных из разных университетов мира, предлагая новые подходы и конструкции, понижали верхнюю оценку сложности умножения матриц. На сегодняшний день уже более 20 лет лучшей известной верхней оценкой является алгоритм Копперсмита и Винограда (опубликованный несколько позже, чем стал известным), использующий практически все предложенные за время изучения задачи подходы, имеющий сложность 0(п2,376) для умножения двух квадратных матриц порядка п (см. [9]).

Нелинейные нижние оценки сложности умножения матриц отсутствуют. В 2002 году Ран Раз доказал нижнюю оценку 0(п2 log п) для сложности умножения квадратных матриц порядка п в модели с ограниченными коэффициентами (см. [16]). Для общего случая известна нижняя оценка числа 2п2 — 1 требуемых активных скалярных умножений алгоритма (являющаяся, очевидно, нижней оценкой и числа всех арифметических операций) (см., например, [1]). В 1999 году Маркус Блезер улучшил этот результат, доказав, что умножение матриц требует не менее |п2 — 3п операций умножения чисел (см. [2]). Амир Шпилька в 2001 году улучшил этот результат для конечных полей: 3п2 — о (п2) дм поля GF{2) и (| + 2tp3x))^2 — о (п2) для поля GF (p) (см. [18]). Для малых значений п лучшей на сегодняшний день является оценка 27?, 2 + п — 2 (п ^ 3), принадлежащая Маркусу Блезеру (см. [4]). Существует гипотеза о том, что в действительности сложность умножения матриц порядка п равна 0(п2) ¦ о (п), однако до сих пор это утверждение не доказано и не опровергнуто (см. [5]).

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

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

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

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

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

2. M. Blaser. A 2.5n2-lower bound for the rank of nx n-matrix multiplication over arbitrary fields. Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS), 45−50, 1999.

3. M. Blaser. Algebras of Minimal Rank over Arbitrary Fields. SIIM Technical Report, 17 p., May 10, 2002.

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

5. P. Biirgisser, M. Clausen, M. Shokrollahi. Algebraic Complexity Theory Springer, 1997.

6. P. Biirgisser, M. Lotz. Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. Journal of the ACM 51(3): 464−482 (2004).

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

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

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

10. M. Ftirer. Faster integer multiplication. Proceedings of STOC 2007, 5766 (2007).

11. M. Kaminski. A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields. SIAM J. Comput. 34(4): 960−992 (2005).

12. J. Laderman. A noncommutative algorithm for multiplying 3×3 matrix using 23 multiplications. Bull. Amer. Math. Soc. (1976) 82, № 1, 126−128.

13. J. Morgenstern. Note on a lower bound of the linear complexity of the fast Fourier transform. J. ACM 20: 305−306 (1973).

14. V. Ya. Pan. Simple multivariate polynomial multiplication. Journal of Symbolic Computation, Volume 18, Issue 3, 183−186 (1994).

15. R. Raz. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002.

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

17. A. Shpilka. Lower bounds for matrix product. In 42nd IEEE Symposium on Foundations of Computer Science, 2001.

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

19. В. Б. Алексеев, А. Д. Поспелов. Сложность умножения в групповой алгебре симметрий квадрата. Тезисы 6-ой Международной конференции «Дискретные модели в теории управляющих систем» (2004), 8−11.

20. В. В. Алексеев, А. Д. Поспелов. О ранге групповых алгебр. «Математические методы решения инженерных задач», 5−25 (2005).

21. В. Б. Алексеев, А. Д. Поспелов. Сложность умножения в некоторых групповых алгебрах. Дискретная математика (2005) 17, № 1, 3−17.

22. Б. Л. Ван дер Варден. Алгебра. М.: Наука, 1979.

23. Э. Б. Винберг. Курс алгебры. М., Изд-во «Факториал Пресс», 2001 г.

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

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

26. А. Д. Поспелов. Ранг коммутативных групповых алгебр над полями комплексных и вещественных чисел. Тезисы докладов XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23−28 мая 2005 г.), с. 125.

27. А. Д. Поспелов. Билинейная сложность умножения в коммутативных групповых алгебрах. Сборник тезисов лучших дипломныхработ 2005 года. Москва, издательский отдел ф-та ВМиК МГУ им. М. В. Ломоносова (2005), с. 75−76.

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