Московский государственный университет

имени М. В. Ломоносова

Факультет вычислительной математики и кибернетики

На правах рукописи

Поспелов Алексей Дмитриевич

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

Специальность 01.01.09 – дискретная математика

и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва – 2008

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук, профессор Алексеев Валерий Борисович.

Официальные оппоненты: доктор физико-математических наук, профессор механико-математического факультета МГУ Гашков Сергей Борисович;

кандидат физико-математических наук, ведущий научный сотрудник ИСП РАН Шокуров Александр Владимирович.

Ведущая организация: Вычислительный центр РАН.

Защита диссертации состоится 31 октября 2008 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП–1, Москва, Ленинские горы, МГУ, 2–ой учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени М. В. Ломоносова http://www.cmc.msu.ru в разделе Наука – Работа диссертационных советов – Д 501.001.44.

Автореферат разослан 29 сентября 2008 г.

Ученый секретарь диссертационного совета профессор Трифонов Н. П.

Общая характеристика работы

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

Особенность данной работы заключается в использовании алгебраических методов.

Пусть A конечномерное линейное пространство над полем k. A называется алгеброй, если в A определено умножение векторов, обладающее свойством ассоциативности и дистрибутивности относительно сложения в A. Пусть a = {a1,..., an } базис в A, и умножение определяется формулами n ai aj = ij a, 1 i, j n.

= Нетрудно видеть, что для умножения двух векторов n n i ai и j aj, i=1 j= где i и j числа из k, являющиеся координатами векторов-множителей в базисе a, по определённым выше формулам необходимо выполнить n2 операций умножения переменных из k и n2 n операций сложения.

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

В 1962 году А. А. Карацуба и Ю. П. Офман предложили алгоритм умножения чисел длины n в двоичной системе счисления со сложностью O(nlog2 3 ). Этот алгоритм легко трансформируется в алгоритм умножения многочленов одного переменного степени n. Таким образом, впервые было установлено, что традиционный алгоритм не является оптимальным. Предложенный алгоритм использовал технику разделяй-ивластвуй и неявно основывался на вычислении и последующей интерполяции многочлена второй степени по трём точкам. Более полно этот подход был использован А. Л. Тоомом в 1963 году, предложившим для любого > 0 алгоритм умножения чисел длины n в двоичной системе счисления сложности основанный на алгоритме умножения многочленов степени n той же сложности. В 1971 году данный результат был улучшен А. Шёнхаге и Ф. Штрассеном, предложившими алгоритмы сложности для умножения многочленов степени n и чисел длины n в двоичной записи. Этот алгоритм оставался асимптотически самым быстрым на протяжении 26 лет и был улучшен в 2007 году Мартином Фюрером, предложившим алгоритм сложности для умножения чисел длины n.

Нетривиальные нижние оценки сложности умножения полиномов известны только в моделях с ограничениями. В общем случае из линейной независимости коэффициентов полинома-произведения следует только, что для умножения полиномов степени n требуется не менее арифметических операций. Большинство асимптотически быстрых алгоритмов основаны на дискретном преобразовании Фурье. В 1973 году Ж. Моргенштерн заметил, что дискретное преобразование Фурье имеет суперлинейную сложность, а именно, если в алгоритме трансформации использовать только коэффициенты, ограниченные некоторой константой. В 2004 году Петер Бюргиссер и Мартин Лотц обобщили эту оценку на произвольные алгоритмы умножения полиномов. Существует гипотеза о том, что в действительности сложность умножения многочленов равна однако до сих пор это утверждение не доказано и не опровергнуто.

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

Нелинейные нижние оценки сложности умножения матриц отсутствуют. В 2002 году Ран Раз доказал нижнюю оценку для сложности умножения квадратных матриц порядка n в модели с ограниченными коэффициентами. Для общего случая известна нижняя оценка числа требуемых активных скалярных умножений алгоритма (являющаяся одновременно нижней оценкой числа всех арифметических операций). В 1999 году Маркус Блезер улучшил этот результат, доказав, что умножение матриц требует не менее операций умножения чисел. Амир Шпилька в 2001 году улучшил этот результат для конечных полей:

Для малых значений n лучшей на сегодняшний день является оценка принадлежащая Маркусу Блезеру. Существует гипотеза о том, что в действительности сложность умножения матриц порядка n равна однако до сих пор это утверждение не доказано и не опровергнуто.

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

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

1. Получение всех максимальных идеалов в групповых алгебрах.

2. Сведение умножения в групповых алгебрах к умножению полиномов одного переменного.

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

Научная новизна. Все результаты диссертации являются новыми.

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

2. Изучены некоторые некоммутативные групповые алгебры, установлены верхние и нижние оценки их сложности и связь сложности умножения в некоммутативных групповых алгебрах со сложностью умножения матриц.

3. Предложен метод умножения полиномов многих переменных оптимальной сложности, основанный на сведении задачи к умножению в групповых алгебрах.

Научная и практическая ценность. Работа имеет теоретическую направленность. Установлена сложность умножения в ряде групповых алгебр, для некоторых алгебр получены нижние и верхние оценки сложности, установлена связь сложности умножения матриц со сложностью умножения в групповых алгебрах.

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

Методы исследования. В диссертации используются методы теории сложности, компьютерной алгебры, теории групп и теории полей.

Публикации и апробирование. Результаты диссертации докладывались на семинаре мехмата МГУ Математические вопросы кибернетики (руководитель академик РАН О. Б. Лупанов), на VI Междунарожной конференции Дискретные модели в теории управляющих систем (Москва, 2004 г.), на XIV Международной конференции Проблемы теоретической кибернетики (Пенза, 2005 г.), на VII Междунарожной конференции Дискретные модели в теории управляющих систем (Москва, 2006 г.), на XIX Международной конференции IEEE Computational Complexity Conference (Прага, 2006 г.), на семинаре факультета информатики университета Саарланда (Саарбрюкен, Германия) Computational Complexity (руководитель профессор М. Блезер), на семинаре факультета информатики университета Технион (Хайфа, Израиль) Algebraic Complexity (руководитель профессор М. Каминский) и на семинаре факультета информатики университета Технион (Хайфа, Израиль) Complexity Theory (руководитель профессор А. Шпилька).

По теме диссертации опубликовано 6 работ.

Структура и объем работы. Диссертация состоит из введения, пяти глав и списка литературы. Объем работы 102 страницы.

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

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

В разделе 1.1 даются основные определения и факты из теории групп.

Теорема 1. Любая коммутативная группа G порядка n 2 разлагается в прямое произведение циклических групп:

брать так, что nµ = pµµ, где pµ простые числа, а dµ > 0 (такие группы Znµ называются примарными), в этом случае представление (1) единственно с точностью до перестановки множителей.

В разделе 1.2 вводятся модель вычисления и постановка задачи. Пусть U, V, W конечномерные линейные пространства над полем k, и :

U V W билинейное отображение. Билинейным вычислением (билинейным алгоритмом) для называется такая последовательность для любых u U, v V r называется длиной билинейного вычисления. Рангом или билинейной сложностью называется длина кратчайшего билинейного вычисления для. Ранг обозначается rk.

Ранг умножения в алгебре A (являющегося билинейнейным отображением A A A) называется рангом алгебры A и обозначается rk A.

Обобщением билинейного вычисления и ранга является квадратичное вычисление и мультипликативная сложность. Квадратичным вычислением (квадратичным алгоритмом) для является такая последовательность (f1, g1, w1,..., f, g, w ), где f, g (U V ), w W, называется длиной квадратичного вычисления. Мультипликативной сложностью называется длина кратчайшего квадратичного вычисления для. Мультипликативная сложность обозначается C().

Мультипликативная сложность умножения в алгебре A называется мультипликативной сложностью алгебры A и обозначается C(A).

Основными характеристиками сложности алгебр в данной работе являются мультипликативная и билинейная сложности умножения.

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

Теорема 2 (А. Алдер, Ф. Штрассен). Для произвольной ассоциативной алгебры A выполняется где t(A) число максимальных двусторонних идеалов A.

Отсюда, в частности, следует, что rk A для которых оценка Алдера-Штрассена совпадает с верхней, называются алгебрами минимального ранга.

Левый (правый, двусторонний) идеал I в A называется нильпотентным, если для некоторого целого числа n выполняется I n = {0}. Сумма всех нильпотентных левых идеалов алгебры A является нильпотентным двусторонним идеалом в A, называется радикалом A и обозначается rad A. Известно, что rad A содержится в любом максимальном двустороннем идеале A. Так, например, если пересечение всех максимальных двусторонних идеалов A равно {0}, то rad A = {0}. Обратно, если пересечение всех максимальных двусторонних идеалов A является левым нильпотентным идеалом, то оно совпадает с rad A.

Элемент a алгебры A называется обратимым, если существует такой a A, что aa1 = a1 a = e, где e единица алгебры. Обозначим множество обратимых элементов алгебры A через A. Алгебра D называется алгеброй с делением, если D = D \ {0}. Алгебра A называется локальной, если фактор-алгебра A/rad A является алгеброй с делением, и A называется основной, если A/rad A является прямым произведением алгебр с делением. Будем называть алгебру A над полем k сверхосновной, если A/rad A k t для некоторого t. Очевидно, что любая сверхосновная алгебра является основной.

Пусть k nn алгебра матриц порядка n n над полем k.

Теорема 3 (М. Блезер). Алгебра A над полем k является алгеброй минимального ранга тогда и только тогда, когда где C1,..., Cs суть локальные алгебры минимального ранга, у которых dim(C /rad C ) 2, то есть C k[X]/(p (X)d ) для некоторого неприводимого над k полинома p, deg p 2, d 1 и k 2 dim C 2, = 1,..., s, а B сверхосновная алгебра минимального ранга над k. B является сверхосновной алгеброй минимального ранга тогда и только тогда, когда найдутся такие w1,..., wm rad B, wi wj = 0, i = j, что 2N (B) 2, где LB и RB суть правый и левый аннигиляторы rad B (то есть множество всех таких x rad B, что x(rad B) = 0, соответственно (rad B)x = 0), а N (B) наибольшее целое j, для коj торого (rad B) = {0}. Любое из чисел s, u может равняться нулю, а множитель B является необязательным.

Также в разделе 1.3 доказывается теорема 4, являющаяся основным инструментом получения нижних и верхних оценок в групповых алгебрах.

Теорема 4. Ортогональное дополнение левого (правого) идеала групповой алгебры A относительно покоординатного скалярного произведения в произвольном групповом базисе является левым (соответственно правым) идеалом.

Глава 2 посвящена коммутативным групповым алгебрам над полями, поддерживающими быстрое преобразование Фурье.

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

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

Теорема 5. Пусть D блочная циклическая матрица (блочного) порядка p над произвольным полем F простой характеристики p, все блоки которой являются квадратными матрицами, Тогда D эквивалентна1 матрице F, В данном случае эквивалентность означает существование невырожденных матриц P и Q, таких что det P · det Q = 1 и F = P DQ. Первое свойство в данном случае необходимо для того, чтобы определители D и F совпадали.

Теорема 6. Пусть поле F имеет характеристику p. Определитель циклической матрицы C, где равен в случае, если p n, Теорема 7. Пусть C где p t и k > 0, над алгебраически замкнутым полем характеристики Тогда Теорема 8. Пусть для каждого, = s,..., 2, блочная циклическая матрица D над полем характеристики p построена из q различных матриц D1, j = 0,..., q 1, q = pr для некоторого натурального r, следующим образом:

При этом матрицы D1 имеют размер 1 1 (q1 = 1, r1 = 0). Тогда где n = s qi порядок матрицы Ds, а di суть различные скалярные элементы i-го столбца матрицы Ds.

В разделе 2.3 устанавливается сложность умножения в групповых алгебрах циклических групп над полями, поддерживающими быстрое преобразование Фурье.

Теорема 9. Пусть алгебраически замкнутое поле F имеет характеристику p, n = pk t, p t. Тогда алгебра F[Zn ] является алгеброй минимального ранга и Попутно устанавливается структура таких алгебр.

Теорема 10. Пусть алгебраически замкнутое поле F имеет характеристику p, n = pk t, p t. Тогда алгебра F[Zn ] является алгеброй минимального ранга и В разделе 2.4 получаются точные оценки сложности умножения в произвольных коммутативных групповых алгебрах над полями, поддерживающими быстрое преобразование Фурье.

Теорема 11. Пусть A коммутативная групповая алгебра над полем F характеристики p, поддерживающим быстрое преобразование Фурье.

Тогда случае Пусть A коммутативная групповая алгебра над полем F характеристики 0, поддерживающим быстрое преобразование Фурье. Тогда В этом случае Глава 3 посвящена коммутативным групповым алгебрам над полем вещественных чисел.

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

Обозначим e(n) = n 2 n.

Теорема 12. Для любого n В разделе 3.2 изучаются произвольные коммутативные групповые алгебры над полем вещественных чисел, определяется структура и устанавливается сложность таких алгебр, вводится понятие константы асимптотики сложности, и доказывается теорема, полностью описывающая спектр таких констант для произвольных последовательностей коммутативных групповых алгебр над полем вещественных чисел.

Теорема 14.

Теорема 15.

Пусть абелева группа G разлагается в прямое произведение циклических групп следующим образом:

Обозначим e(G) = e(n1 ) · · · e(nt ).

Теорема 16. Пусть G абелева группа. Тогда Теорема 17. Пусть G Пусть {Ai } последовательность алгебр над одним и тем же полем k, причём dim Ai = ni и ni. Назовём константой асимптотики сложности величину если данный предел существует.

Теорема 18. 1. Пусть {Ai } последовательность групповых алi= гебр абелевых групп над C. Тогда C(A) = 1.

2. Пусть Для каждого m, m = 0, 1, 2,..., существует такая последовательность групповых алгебр Am i=1 абелевых групп над R, что для любого m константа асимптотики сложности равна C(Am ) = 3. Пусть {Ai } произвольная последовательность групповых алi= гебр абелевых групп над R, для которой существует C(A). Тогда существует m 0 : C(A) = Cm Глава 4 посвящена задаче умножения полиномов одного и нескольких переменных.

В разделе 4.1 вводятся основные понятия и постановка задачи.

В разделе 4.2 приводятся лучшие известные оценки сложности умножения полиномов в различных моделях вычисления над различными полями.

В разделе 4.3 демонстрируется способ получения быстрых алгоритмов умножения полиномов многих переменных посредством сведения к умножению в коммутативных групповых алгебрах.

Теорема 19. Пусть p1 и p2 полиномы m переменных X1,..., Xm степеней dµ по переменным Xµ, dµ > 0, 1 µ m над полем k, содержащим все корни степени M = µ=1 (2dµ +1) из 1. Пусть также характеристика поля k, и M = pd t, где p t. Тогда существует билинейный алгоритм умножения полиномов p1 и p2 длины 2M t.

Глава 5 посвящена некоторым некоммутативным алгебрам.

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

Теорема 20. Имеет место изоморфизм:

Теорема 21. C[S3 ] является алгеброй минимального ранга.

Теорема 22. Для сложности умножения в C[S3 ] выполняется Теорема 23. Алгебра C[S3 ] содержит единственную подалгебру, изоморфную алгебре матриц C22.

В разделе 5.2 доказаны теоремы о структуре и сложности групповой алгебры симметрий квадрата.

Теорема 24. C[Q] C22 C4.

Теорема 25. rkC[Q] = 11.

Гипотеза о прямой сумме в теории сложности алгебр гласит, что для любых алгебр A и B над полем k справедливо rk A B = rk A + rk B.

На сегодняшний день эта гипотеза не доказана и не опровергнута.

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

Теорема 26. Пусть характеристика k отлична от 2. Тогда в k[A4 ] существует подалгебра, изоморфная k 33.

Теорема 27. Имеет место изоморфизм а также сложностное равенство Теорема 28. Имеет место изоморфизм а также следующая нижняя оценка сложности умножения матриц третьего порядка Теорема 29. Справедливо, по крайней мере, одно из следующих утверждений:

1. rk C33 < rk R33, 2. rk C[A4 ] < rk R[A4 ], 3. гипотеза о прямой сумме является неверной.

1. Разработан метод получения нижних оценок мультипликативной сложности групповых алгебр.

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

3. Описана структура и мультипликативная сложность коммутативных групповых алгебр над полем вещественных чисел. Полностью описан спектр констант асимптотики сложности всех таких алгебр.

4. Разработан метод быстрого умножения полиномов многих переменных над полями, поддерживающими быстрое преобразование Фурье, основанный на умножении в групповых алгебрах.

5. Изучены некоммутативные групповые алгебры групп подстановок третьего порядка, симметрий квадрата и чётных подстановок четвёртого порядка, установлена связь сложности умножения в этих алгебрах со сложностью умножения квадратных матриц второго и третьего порядков.

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

Москва, издательский отдел ф-та ВМиК МГУ им. М. В. Ломоносова (2004), 8–11.

2. Алексеев В. Б., Поспелов А. Д. О ранге групповых алгебр. Математические методы решения инженерных задач. Москва, Министерство обороны Российской Федерации (2005), 5–25.

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

4. Поспелов А. Д. Ранг коммутативных групповых алгебр над полями комплексных и вещественных чисел. Тезисы докладов XIV Международной конференции Проблемы теоретической кибернетики (Пенза, 23–28 мая 2005 г.). Издательство центра прикладных исследований при механико-математическом факультете МГУ (2005), 5. Поспелов А. Д. Билинейная сложность умножения в коммутативных групповых алгебрах. Сборник тезисов лучших дипломных работ 2005 года. Москва, издательский отдел ф-та ВМиК МГУ им.

М. В. Ломоносова (2005), с. 75–76.

6. Поспелов А. Д. О сложности умножения полиномов и матриц.

Сборник статей молодых учёных факультета ВМиК МГУ, 2008, выпуск №5. Москва, издательский отдел ф-та ВМиК МГУ им. М. В.

Ломоносова (2008), с. 83–97.