Мультипликативная сложность умножения в алгебрах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

005054262

Чокаев Бекхан Вахаевич

Мультипликативная сложность

умножения в алгебрах

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

- I НОЯ 2012

Москва - 2012

005054262

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

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

профессор Алексеев Валерий Борисович.

Официальные оппоненты: доктор физико-математических наук,

профессор Гашков Сергей Борисович;

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

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

имени А. А. Дородницына.

Защита диссертации состоится 16 ноября 2012 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/.

Автореферат разослан {2, октября 2012 г.

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

Н.П. Трифонов

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

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

Одной из наиболее важных и интересных задач в данной области является задача сложности умножения в алгебре матриц. В 1969 году Ф. Штрассен опубликовал алгоритм умножения квадратных матриц порядка п арифметической сложности 0(п'°^Т), тем самым впервые доказав, что традиционный алгоритм умножения матриц "строка на столбец" не является оптимальным2. После выхода статьи Штрассена эта задача привлекла большое внимание со стороны математиков из разных стран. Несколько групп ученых из разных университетов мира, предлагая новые подходы и конструкции, понижали верхнюю оценку сложности умножения матриц. На сегодняшний день лучшей известной верхней оценкой для умножения двух квадратных матриц порядка п является 0(п2'373)3'4. Существует гипотеза о том, что сложность умножения матриц порядка п равна о(п2+е)

'Р. Biirgisser, M. Clausen, M. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.

JV. Strossen. Gaussian elimination is not optimal. Numcr. Math. 13, 354-356 (1969).

3 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.

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

для любого £, однако до сих пор это утверждение не доказано и не опровергнуто5.

В 2003 году Генри Коэн и Кристофер Уманс предложили новый подход для получения верхних оценок сложности умножения матриц, основанный на вложениях в групповые алгебры6. Групповой называется алгебра, в которой существует базис такой, что множество элементов, входящих в этот базис, образуют группу относительно умножения в алгебре. Было показано, что, если сложность умножения в групповых алгебрах — почти линейна относительно размерности алгебры, то сложность умножения квадратных матриц порядка п — почти квадратична относительно п. В 2005 году этим методом были получены алгоритмы умножения матриц минимальной сложности среди всех известных алгоритмов7. Эти результаты стимулировали рост интереса к групповым алгебрам. В кандидатской диссертации А. Д. Поспелова были исследованы коммутативные групповые алгебры над алгебраически замкнутыми полями и полем вещественных чисел8. Им были установлены точные значения сложности умножения в таких групповых алгебрах.

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

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

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

fiH. Cohn, С. Umans. A Group-Theoretic Approach to Fast Matrix Multiplication.//Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, p. 438-449.

7H. Colm, R. D. Kleinberg, В. Szegedy, С. Umans. Group-theoretic Algorithms for Matrix Multiplication.// Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, p. 379-388.

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

9А. Alder, V. Strassen. On the algorithmic complexity of associative algebras. Theoret. Coinput. Sei., 15:201-211, 1981.

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

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

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

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

'"Markus Bläser. A Complete Oiaracterization of the Algebras of Minimal Bilinear Complexity. SIAM J. Comput., 34(2):277-298, 2004.

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

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

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

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

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

Апробация результатов. Результаты, полученные в диссертации, докладывались и обсуждались на международных конференциях: VIII международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2009), X международном семинаре «Дискретная математика и её приложения» (Москва, 2010), XVI международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 2011), XVIII международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2011» (Москва, 2011), XI международном семинаре «Дискретная математика и её приложения» (Москва, 2012), XXVII международной конференции «IEEE Computational Complexity Conference» (Порту, Португалия, 2012).

Кроме того, результаты обсуждались на научных семинарах: «Дискретная математика и математическая кибернетика» и «Дискретный ана-

лиз» кафедры математической кибернетики факультета ВМК МГУ, Кол-могоровском семинаре по сложности вычислений и сложности определений кафедры математической логики и теории алгоритмов механико-математического факультета МГУ, семинаре «Computational Complexity» факультета «Computer Science» университета Саарланда (Германия).

Публикации. Результаты автора по теме диссертации опубликованы в 7 работах, список которых приводится в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и библиографии, включающей 57 наименований. Общий объем диссертации составляет 80 страниц.

Краткое содержание работы

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

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

Определение 1. Пусть U,V,W — конечномерные линейные пространства над полем к, итр: UxV-^W — билинейное отображение. Билинейным вычислением (билинейным алгоритмом) для тр называется такая последовательность (fi,guw 1,..., /г, gr, wr), где /р е U\gp € V*12,wp € W, 1 < р < г, что для любых и е U, v 6 V

г

■ф{и, v) = Yl fp{u)gp{v)wp.

Р= i

Число г называется длиной билинейного вычисления. Рангом или билинейной сложностью ф называется длина кратчайшего билинейного вычисления для -ф. Ранг ф обозначается R(ifi).

Ранг умножения в алгебре А (являющегося билинейным отображением Ах А —» Л) называется рангом алгебры А и обозначается R(A).

12Через U',V' обозначены двойственные пространства к пространствам U, V соответственно.

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

Определение 2. Квадратичным вычислением (квадратичным алгоритмом) для ф называется такая последовательность (Л,3ь Щ, ■ ■ ■, fu 91, где fx, 9х 6 (U х V)*, wx е W, 1 < Л < I, что для любых uß U, v € V

i

ф{и, v) = Ys /а(". v)wx.

Л—1

Число I называется длиной квадратичного вычисления. Мультипликативной сложностью ф называется длина кратчайшего квадратичного вычисления для ф. Мультипликативная сложность ф обозначается С(ф).

Мультипликативная сложность умножения в алгебре А называется мультипликативной сложностью алгебры А и обозначается С {А). Очевидно, для любого ф справедливо С(ф) < Л{ф).

Теорема 1 (А. Алдер, Ф. Штрассен13). Для произвольной ассоциативной алгебры А выполняется

С{А)> 2áim A-t{A), (1)

где t{A) - число максимальных двусторонних идеалов А.

Алгебра, для которой оценка (1) совпадает с верхней оценкой, называется алгеброй минимальной мультипликативной сложности. Если оценка (1) выполняется как равенство для ранга, то есть R{A) = 2 dim А - t(A), то алгебра называется алгеброй минимального ранга. Очевидно, что произвольная алгебра минимального ранга является алгеброй минимальной мультипликативной сложности.

Определение 3. Пусть А — алгебра над полем к размерности п, и пусть oí,...,а« — некоторый базис А. Если множество {oi,...,on} образует группу относительно умножения в А, то такой базис называется групповым базисом, а алгебра соответственно групповой алгеброй. Обратно, пусть Q — {5ь ...,дп} — группа порядка п, и к — поле. Тогда множество формальных сумм

В = {агдг + • • • + апдп\ос„ ек, 1 <и<п}

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

с умножением, определяемым по правилу

¿><И (¿/и,) = £ ( £ «Л

/ \/"=1 / «=1 \^д„9„=дк )

образует групповую алгебру. Будем обозначать групповую алгебру группы С над полем к через к[С). Очевидно, что к[0\ коммутативна тогда и только тогда, когда й — абелева.

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

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

Обозначим через <0> поле рациональных чисел. Пусть — групповая алгебра циклической группы над полем рациональных чисел. Циклическая группа Ъп определяется законом умножения:

Зі

.g.-Í9i+j, i+j<n, 3 I 9i+j-n, i+j>n.

Прежде чем формулировать теорему о групповой алгебре Q[Z„] введем понятие кругового многочлена. Круговым многочленом называется многочлен вида

к

где произведение берётся по всем натуральным числам к, меньшим п и взаимно простым с п, а = cos ^ + г sin ^ — комплексный корень степени п из единицы. Обозначим через <0>[Х]/(Ф^(Х)) — фактор-алгебру алгебры многочленов от переменной X над полем рациональных чисел по модулю многочлена Ф^Х).

Теорема 2. Пусть Q[Z„] - групповая алгебра циклической группы порядка п над полем рациональных чисел, и а равно количеству делителей числа п. Тогда алгебра Q[Z„] является алгеброй минимального ранга, 5„]) = 2п — а, и

~ * «ВД(-ВД). (2)

а\п

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

Пусть G„ — произвольная абелева группа порядка п — ■ ■■Рк3', где Р1,Р2, ■ --,Ра — попарно различные простые числа. Так как произвольная абелева группа изоморфна прямому произведению примарных циклических групи, то будем считать, что Gn определяется следующим образом:

Gn = Gp^ х Gp*2 х ... х Gpk,. (3)

(4)

Si

о = fci0 < kil < ki2 < . . • < kiSi = li, "^kij = ku і = 1,...,s. (5)

j=і

Пусть m = p[lp% ■ • • Pll• Тогда m делит п,ит = п«С„ = 2». Далее, пусть числа и п v таковы, что 1 < и < /¿, kiv < и < fciiU+i, т. е. v однозначно определяется по и. Тогда

Мч-v) _ (u-l)(Si-l>) «

= 1, <ТР? = Р<<" • Рі „ -, где tiu = Y, *У ■ (6)

Pi Pi j=1

Определим теперь числа Od, где d — произвольный делитель числа т, а также число а, зависящее от структуры группы Gn:

d - p^pf .. ,pus0 < щ < li, =>ad = -crp?-...- Op«., (7)

d\m •=1 u=0

Теорема 3. Пусть Q[G„] — произвольная коммутативная групповая алгебра размерности п над полем рациональных чисел. Тогда алгебра Q[G„] является алгеброй минимального ранга, ,R(Q[Gn]) = 2п — а, и

Q[Gn] S х (а^І/Фй)^. (9)

d\m

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

Обозначим через F произвольное поле характеристики 0. Рассмотрим групповую алгебру F[G„] абелевой группы Gn. Будем считать, что G„ определяется согласно формулам (3) — (5).

Как известно, произвольное поле характеристики 0 содержит подполе, изоморфное полю рациональных чисел. Поэтому будем считать, что поле Ж является расширением поля (2.

Для любого натурального й многочлен Фа(Х) имеет целые коэффициенты, следовательно, он является многочленом над полем Обозначим через ті число неприводимых над полем Р многочленов, произведение которых равно многочлену Фа(Х). Тогда можно записать

где многочлены /фРО, і = 1, ...,г«г, неприводимы над полем I. Пусть числа т,а,<л, определяются, в зависимости от группы по формулам (6) — (8). Определим константу сгр, зависящую от поля Ж и группы Єп, таким образом

<i|m

Справедлива следующая теорема, которая является обобщением теоремы 3.

Теорема 4. Пусть F[G„] — произвольная коммутативная групповая алгебра размерности п над полем характеристики 0. Тогда алгебра F[G„] является алгеброй минимального ранга, fl(F[Gn]) = 2n - crF < 2п — а, и

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

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

Все поля, рассматриваемые в третьей главе, имеют характеристику р, где р произвольное простое число. Разобьём множество 0 — всех абелевых групп, на последовательность вложенных подмножеств. Пусть Сдг — произвольная абелева группа порядка N. Тогда группу Єн можно однозначно представить в виде прямого произведения примарных циклических групп:

®d(x) = u(x)-ux)....-fdrd(x)

(10)

F[G„] £ х (F[*]W = х х (ВД/Ф-Г-

d\m d\mj=1

(И)

С?^ = 2р», х2^х...х где Р1,Р2, ...,Рг~ простые числа. Будем говорить, что ЄхЄ би если пе более чем і из этих простых чисел совпадают с р. Очевидно, что Оі С бі+и и б = бо и б\ и ... и бі и • • ■•

Пусть Р — произвольное поле характеристики р (если I — конечное, то обозначим число его элементов через <?). Пусть Єн Є бі — произвольная абелева группа порядка N. принадлежащая множеству би и пусть N = ркп = Р^Р^2 ■ ■ -Ргг, где р \ п, Р1,Р2, ■ ■ ■ ,Рг - попарно различные простые числа. Тогда

= г? х <3П, (12)

где сп — произвольная абелева группа порядка п. Пусть Єп определяется согласно формулам (3)-(5). Пусть тп = р1?р% .. .ф. Обозначим

= Г 2р*йт - 2, если вт > 1, (13)

\ 2рк - 4, если = 1, где Эт — мультипликативная степень числа д по модулю т, то есть такое минимальное натуральное число, что - 1 делится на т. Теорема 5. Пусть ¥[<3^] - групповая алгебра абыевой группы порядка N над произвольным полем простой характеристики. Алгебра Р^дг] являлется алгеброй минимального ранга т.огда и только тогда, когда выполняются два условия:

1) группа Слг принадлежит множеству групп би

2) если ¥ — конечное поле, то число его элементов д > £.

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

Из теоремы 5 следует, что по данной групповой алгебре над ко-

нечным полем ^ мощности д, вычислив £ по формуле (13), можно определить, является ли эта алгебра алгеброй минимального ранга. Если является, то можно вычислить ар, и найти точное значение для Если она не является алгеброй минимального ранга, то нижняя оценка 2ДГ _ ар остается справедливой, тогда как о верхней оценке уже ничего сказать нельзя. Однако, удается доказать, что билинейная сложность умножения в алгебре Рч[Сц] растет линейно относительно её размерности.

Теорема 6. Пусть - групповая алгебра абелевой группы порядка N

над произвольным полем характеристики р, Сдг Є бі- Тогда существует константа Сі, зависящая только от множества бі, такая, что

< СІЛГ. (14)

Пусть Gi, G2,..., Gn,... — последовательность групп такая, что Gn S Qin \ Qln-1, |G„| —»• 00 при 71 oo, и sup/„ = I < 00. Из теоремы 6 следует, что над произвольным полем F характеристики р верно, что Ä(F[G„]) < С • dimF[Gn], где константа С не зависит от п. При этом, остается открытым вопрос о том, как растет билинейная сложность ñ(F[Gn]) при п —> оо, если supin — 00' Для доказательства некоторой нетривиальной нижней оценки для такой последовательности групповых алгебр над произвольным полем простой характеристики в диссертационной работе используется следующая теорема14:

Теорема 7. Пусть А — ассоциативная алгебра. Для всех m, п > О, С (А) > dim А + dim(rad/l)m + dim(rad¿)" - din^rad^)"4^1.

При помощи этой теоремы Блезер построил последовательность явно заданных алгебр Ап с наилучшей среди известных нижней оценкой мультипликативной сложности, а именно, с оценкой (3 — о( 1)) dim Ап. Оказывается, что последовательность алгебр с такой нижней оценкой можно выбрать и среди коммутативных групповых алгебр.

Теорема 8. Пусть F[Gn] — последовательность групповых алгебр над полем F характеристики р такая, что G„ € Qn\ Qn-\, и dimF[G„] = Тогда

C(F[G„]) > (3 - o(l)) dimF[G„], при n ->■ 00.

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

В разделе 4.1 приводятся постановка и актуальность задачи, формулируется основная теорема главы (теорема 11).

Много работ в алгебраической теории сложности посвящено описанию алгебр минимального ранга с точки зрения их алгебраической структуры. Одной из мотиваций этих работ являлось найти сложность умножения матриц малого порядка. Давно известно, что алгебра &2х2 — алгебра матриц размерности 2x2, является алгеброй минимального ранга. Долгое время открытой проблемой было определить, является ли алгебра к3x3 алгеброй минимального ранга15. Один способ решения этой задачи — описать все

14Markus Blaser. Improvements of the Aider-Strassen Bound: Algebras with Nonzero Radical. Institut für Theoretische Informatik, Germany.

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

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

7 3x3

проверить выполнение этих свойств для к

Де Грут был первым, кто нашел описание всех алгебр с делением D минимального ранга16. Над бесконечным полем все такие алгебры являются простыми расширениями поля к. Если к конечное, то D имеет минимальный ранг, если вдобавок #fc > 2 dim D - 2, что следует из описания всех алгоритмов умножения многочленов по модулю некоторого неприводимого многочлена17. Де Грут и Хейнц18 исследовали коммутативные алгебры минимального ранга над бесконечным полем. Далее Бучи и Клаузен19 описали все локальные алгебры минимального ранга над бесконечным полем. Затем Хейнц и Моргенштерн20 описали все основные алгебры над алгебраически замкнутыми полями. Наконец, все полупростые алгебры над произвольными полями и все алгебры над алгебраически замкнутыми полями были найдены Блезером21. Важным побочным эффектом этого результата стало то, что алгебра fc3x3 не является алгеброй минимального ранга. Полное и окончательное описание всех алгебр минимального ранга было получено Блезером в 2002 году22.

Теорема 9 (М. Блезер). Алгебра А над полем к является алгеброй минимального ранга тогда и только тогда, когда

A = C1X-"XC,X ft2*2 х ••• х fc2x2 xg, (15)

и раз

где Ci,..., С3 — локальные алгебры, минимального ранга, для которых dimtCV/radCV) > 2, то есть Са к[Х]/{р<г(ХУ°) для некоторого неприводимого над к полинома ра, degр„ > 2, da > 1 и > 2dimCff - 2, а = 1,..., s, а В — сверхосновная алгебра минимального ранга над к. Сверхосновная алгебра В является алгеброй минимального ранга тогда и только тогда, когда найдутся такие ..., wm е radB, w\ 0, WiWj = 0, i ф j,

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

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

18Hans F. de Groote and .loos Heintz. Commutative algebras of minimal rank. Lin. Alg. Appl., 55:37-68, 1983.

19Werner Biichi and Michael Clausen. On a class of primary algebras of minimal rank. Lin. Alg. Appl., 69:246-268, 1985.

20Joos Heintz and Jacques Morgcnstern. 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.

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

"Markus Bliiser. A Complete Characterization of the Algebras of Minimal Bilinear Complexity. SIAM J. Comput., 34(2):277-298, 2004.

что

rad В = LB + BwiB + • • • + BwmB = RB + BwxB + • • • + BwmB

и #k > 2N(B) — 2, где Lb и Rb суть правый и левый аннигиляторы radß (то есть множество всех таких х Є radß, что x(radВ) = {0}, соответственно (radВ)х = {0}); a N(B) — наибольшее целое j, для которого (radjE?)7 {0}. Любое из чисел s,u может равняться нулю, а множитель В является необязательным.

Так как доказывать нижние оценки для мультипликативной сложности обычно сложнее, чем для ранга, то в отличие от алгебр минимального ранга для алгебр минимальной мультипликативной сложности результатов было получено немного. Один известный результат принадлежит Фейгу23, который дополняет описание алгебр с делением минимального ранга Де Грута:

Теорема 10 (Фейг).

1. Алгебра с делением D имеет минимальную мультипликативную сложность тогда и только тогда, когда она имеет минимальный ранг.

2. Более того, каждый оптимальный квадратичный алгоритм для такой алгебры является билинейным, то есть после перестановки некоторых /л с дх, имеем

/л(х, у) = f\(x, 0) и дх(х, у) = 0Л(О, у) для всех х,у Є D.

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

Теорема 11. Алгебра А над произвольным полем является алгеброй минимальной мультипликативной сложности тогда и только тогда, когда она является алгеброй минимального ранга.

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

Теорема 12. Сверхосновная алгебра А над произвольным полем к имеет минимальную мультипликативную сложность тогда и только тогда, когда она имеет минимальный ранг.

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

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

Теорема 13. Локальная алгебра А над произвольным полем к имеет минимальную мультипликативную сложность тогда и только тогда, когда она имеет минимальный ранг.

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

Теорема 14. Алгебра А над произвольным полем к такая, что А/ гасі А = к2*2, имеет минимальную мультипликативную сложность т.огда и только тогда, когда она имеет минимальный ранг.

В разделе 4.5 приводится доказательство основной теоремы 11 на основании результатов разделов 4.2, 4.3 и 4.4.

Раздел 4.6 посвящен обобщению второй части теоремы Фейга для локальных и сверхосновных алгебр. Вводится понятие почти билинейного алгоритма умножения в алгебре. Доказывается теорема 15 о том, что любой квадратичный алгоритм для умножения в локальной или сверхосновной алгебре является почти билинейным. Однако показывается, что существуют квадратичные алгоритмы для таких алгебр, не являющиеся билинейными.

Теорема 15. Пусть А — локальная или сверхосновная алгебра минимальной мультипликативной сложности. Тогда любой оптимальный квадратичный алгоритм /3 = (/і, ди гоь ..., /г, де, иіе) для А является почти билинейным. В частности, если ги\ £ Ьа П Яа для всех X, то ¡3 является билинейным.

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

Пример 1. Пусть к — поле характеристики отличной от двух. Алгебра к[Х]/(Х2) является локальной и сверхосновной, но имеет квадратичный алгоритм, который не является билинейным (но естественно является почти билинейным): мы можем вычислить коэффициенты (а + 6Х)(а' + 6'Х) как аа' и аЬ' + Ьа' = \{Ь + Ь')(а + а') + - + а')- Заметим, что

X Є Ьк\ху{Хг) = Кк[Х\КХ*У

Основные результаты, выносимые на защиту

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

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

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

Благодарности

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

физико-математических наук, профессору Алексееву Валерию Борисовичу

за постановку задачи и постоянное внимание к работе.

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

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

[2] Чокаев Б. В. О сложности умножения в коммутативных групповых алгебрах. // Труды VIII Международной Конференции «Дискретные

модели в теории управляющих систем», с. 351-356. Изд-во Макс Пресс, Москва, 2009.

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

[4] Чокаев Б. В. Сложность умножения в коммутативных групповых алгебрах над полями характеристики 0. // Вестник МГУ, серия 15, № 4, стр. 30-40. Изд-во МГУ, Москва, 2010.

[5] Чокаев Б. В. Сложность умножения в коммутативных групповых алгебрах над полями простой характеристики. // Дискретная математика, т. 22, вып. 4, стр. 121-137. "Наука", Москва, 2010.

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

[7] Markus Blaser, Bekhan Chokaev. Algebras of minimal multiplicative complexity. // Proc. 27th Ann. IEEE Computational Complexity Conference (CCC), 224-234, 2012.

Напечатано с готового оригинал-макета

Подписано в печать 05.10.2012 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 382.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8-495-939-3890. Тел./факс 8495-939-3891.

Введение

1 Оценки умножения в алгебрах

1.1 Основные понятия.

1.2 Модель вычислений.

1.3 Используемые методы.

2 Групповые алгебры над полями характеристики

2.1 Алгебра циклической группы над рациональным полем.

2.2 Произвольные алгебры над рациональным полем.

2.3 Алгебры над произвольным полем характеристики нуль.

3 Групповые алгебры над полями простой характеристики

3.1 Групповые алгебры минимального ранга.

3.1.1 Алгебры над конечным полем.

3.1.2 Алгебры над бесконечным полем.

3.1.3 Алгебры пе минимального ранга.

3.2 Верхняя и нижняя оценки мультипликативной сложности.

4 Алгебры минимальной мультипликативной сложности

4.1 Оценка Алдера-Штрассена и алгебры минимальной сложности.

4.2 Сверхосновные алгебры.

4.3 Локальные алгебры.

4.4 Алгебры с условием А/ тзЛА = к2x

4.5 Главный результат.

4.6 Почти билинейные вычисления

Алгоритмическое решение задач всегда было одним из основных предметов математики. В течение долгого времени такие решения были основаны на интуитивных соображениях. К началу 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 Bläser. 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 Bläser. Lower bounds for the multiplicative complexity of matrix multiplication. Comput. Complexity, 8:203-226, 1999.

6. Markus Bläser. Lower bounds for the bilinear complexity of associative algebras. Comput. Complexity, 9:73-112, 2000.

7. Markus Bläser. 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 Bläser. Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. Institut für Theoretische Informatik, Germany.

9. Markus Bläser. On the complexity of the multiplication of matrices of small formats. J. Complexity, 19(1): 43-60, 2003.

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

11. Markus Bläser, 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 Büchi and Michael Clausen. On a class of primary algebras of minimal rank. Lin. Alg. Appl., 69:246-268, 1985.

14. P. Bürgisser, 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.