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

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

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

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

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

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

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

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

кибернетика

АВТОРЕФЕРАТ

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

Москва 2012

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

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

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

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

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

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

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

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

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

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

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

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

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

Одной из наиболее важных и интересных задач в данной области является задача сложности умножения в алгебре матриц. В 1969 году Ф.

Штрассен опубликовал алгоритм умножения квадратных матриц порядка n арифметической сложности O(nlog2 7 ), тем самым впервые доказав, что традиционный алгоритм умножения матриц “строка на столбец” не является оптимальным2. После выхода статьи Штрассена эта задача привлекла большое внимание со стороны математиков из разных стран. Несколько групп ученых из разных университетов мира, предлагая новые подходы и конструкции, понижали верхнюю оценку сложности умножения матриц.

На сегодняшний день лучшей известной верхней оценкой для умножения двух квадратных матриц порядка n является O(n2,373 )3,4. Существует гипотеза о том, что сложность умножения матриц порядка n равна o(n2+ ) P. Brgisser, M. Clausen, M. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.

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

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. Групповой называется алгебра, в которой существует базис такой, что множество элементов, входящих в этот базис, образуют группу относительно умножения в алгебре. Было показано, что, если сложность умножения в групповых алгебрах почти линейна относительно размерности алгебры, то сложность умножения квадратных матриц порядка n почти квадратична относительно n. В 2005 году этим методом были получены алгоритмы умножения матриц минимальной сложности среди всех известных алгоритмов7. Эти результаты стимулировали рост интереса к групповым алгебрам. В кандидатской диссертации А.

Д. Поспелова были исследованы коммутативные групповые алгебры над алгебраически замкнутыми полями и полем вещественных чисел8. Им были установлены точные значения сложности умножения в таких групповых алгебрах.

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

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

Другой целью диссертации является установление алгебраической структуры алгебр минимальной мультипликативной сложности. В 1981 году Алдер и Штрассен доказали свою фундаментальную нижнюю оценку для мультипликативной сложности умножения в произвольной ассоциативной алгебре с единицей9. Так как мультипликативная сложность является обобщением понятия ранга, то оценка Алдера-Штрассена выполняется также для ранга умножения в алгебре. Практически сразу возникла задача описания алгебр минимального ранга с точки зрения их алгебраической Алексеев В. Б. Сложность умножения матриц. Обзор. Киберн. сб. (1988) 25, 189–236.

H. Cohn, C. 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.

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

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

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

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

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

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

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

Научная новизна. В работе доказано, что любая групповая алгебра абелевой группы над произвольным полем характеристики нуль является алгеброй минимального ранга. Описаны структура и мультипликативная Markus Blser. A Complete Characterization 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), Х международном семинаре Дискретная математика и её приложения (Москва, 2010), XVI международной конференции Проблемы теоретической кибернетики (Нижний Новгород, 2011), XVIII международной научной конференции студентов, аспирантов и молодых ученых Ломоносов – 2011 (Москва, 2011), ХI международном семинаре Дискретная математика и её приложения (Москва, 2012), XXVII международной конференции IEEE Computational Complexity Conference (Порту, Португалия, 2012).

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

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

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

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

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

Определение 1. Пусть U, V, W конечномерные линейные пространства вычислением (билинейным алгоритмом) для называется такая последовательность (f1, g1, w1,..., fr, gr, wr ), где f U, g V 12, w W, Число r называется длиной билинейного вычисления. Рангом или билинейной сложностью называется длина кратчайшего билинейного вычисления для. Ранг обозначается R().

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

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

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

Определение 2. Квадратичным вычислением (квадратичным алгоритмом) для называется такая последовательность (f1, g1, w1,..., fl, gl, wl ), Число l называется длиной квадратичного вычисления. Мультипликативной сложностью называется длина кратчайшего квадратичного вычисления для. Мультипликативная сложность обозначается C().

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

Очевидно, для любого справедливо C() R().

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

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

Определение 3. Пусть A алгебра над полем k размерности n, и пусть группу относительно умножения в A, то такой базис называется групповым базисом, а алгебра соответственно групповой алгеброй. Обратно, пусть G = {g1,..., gn } группа порядка n, и k поле. Тогда множество формальных сумм A. Alder, V. Strassen. On the algorithmic complexity of associative algebras. Theoret. Comput. Sci., 15:201–211, 1981.

с умножением, определяемым по правилу образует групповую алгебру. Будем обозначать групповую алгебру группы G над полем k через k[G]. Очевидно, что k[G] коммутативна тогда и только тогда, когда G абелева.

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

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

Обозначим через Q поле рациональных чисел. Пусть Q[Zn ] групповая алгебра циклической группы над полем рациональных чисел. Циклическая группа Zn определяется законом умножения:

Прежде чем формулировать теорему о групповой алгебре Q[Zn ] введем понятие кругового многочлена. Круговым многочленом называется многочлен вида где произведение берётся по всем натуральным числам k, меньшим n и взаимно простым с n, а n = cos 2 + i sin 2 комплексный корень степени n из единицы. Обозначим через Q[X]/(d (X)) фактор-алгебру алгебры многочленов от переменной X над полем рациональных чисел по модулю многочлена d (X).

Теорема 2. Пусть Q[Zn ] групповая алгебра циклической группы порядка n над полем рациональных чисел, и равно количеству делителей числа n. Тогда алгебра Q[Zn ] является алгеброй минимального ранга, R(Q[Zn ]) = 2n, и В разделе 2.2 доказывается теорема 3, которая является обобщением теоремы 2 на случай групповой алгебры произвольной абелевой группы над полем рациональных чисел. Устанавливается структура и мультипликативная сложность умножения в такой групповой алгебре.

Пусть Gn произвольная абелева группа порядка n = pk1 pk2... pks, где p1, p2,..., ps попарно различные простые числа. Так как произвольная абелева группа изоморфна прямому произведению примарных циклических групп, то будем считать, что Gn определяется следующим образом:

Пусть m = pl1 pl2... pls. Тогда m делит n, и m = n Gn Zn. Далее, пусть числа u и v таковы, что 1 u li, kiv < u ki,v+1, т. е. v однозначно определяется по u. Тогда Определим теперь числа d, где d произвольный делитель числа m, а также число, зависящее от структуры группы Gn :

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

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

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

Для любого натурального d многочлен d (X) имеет целые коэффициенты, следовательно, он является многочленом над полем F. Обозначим через rd число неприводимых над полем F многочленов, произведение которых равно многочлену d (X). Тогда можно записать где многочлены fdj (X), j = 1,..., rd, неприводимы над полем F. Пусть числа m,, d, определяются, в зависимости от группы Gn, по формулам (6) (8). Определим константу F, зависящую от поля F и группы Gn, таким образом Справедлива следующая теорема, которая является обобщением теоремы Теорема 4. Пусть F[Gn ] произвольная коммутативная групповая алгебра размерности n над полем характеристики 0. Тогда алгебра F[Gn ] является алгеброй минимального ранга, R(F[Gn ]) = 2n F 2n, и Третья глава посвящена коммутативным групповым алгебрам над полями простой характеристики. Переход к рассмотрению полей простой характеристики значительно меняет ситуацию. Структура групповых алгебр над такими полями оказывается более разнообразной, чем над полями характеристики нуль, и как следствие, существуют коммутативные групповые алгебры, не являющиеся алгебрами минимального ранга.

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

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

GN Zpk1 Zpk2... Zpkr, где p1, p2,..., pr простые числа. Будем гоr ворить, что GN Gi, если не более чем i из этих простых чисел совпадают Пусть F произвольное поле характеристики p (если F конечное, то обозначим число его элементов через q). Пусть GN G1 произвольная абелева группа порядка N, принадлежащая множеству G1, и пусть N = pk n = pk p11 pk2... pkr, где p n, p1, p2,..., pr попарно различные простые числа. Тогда где Gn произвольная абелева группа порядка n. Пусть Gn определяется согласно формулам (3)–(5). Пусть m = pl1 pl2... plr. Обозначим где sm мультипликативная степень числа q по модулю m, то есть такое минимальное натуральное число, что q sm 1 делится на m.

Теорема 5. Пусть F[GN ] групповая алгебра абелевой группы порядка N над произвольным полем простой характеристики. Алгебра F[GN ] являлется алгеброй минимального ранга тогда и только тогда, когда выполняются два условия:

1) группа GN принадлежит множеству групп G1, 2) если F конечное поле, то число его элементов q t.

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

Из теоремы 5 следует, что по данной групповой алгебре Fq [GN ] над конечным полем Fq мощности q, вычислив t по формуле (13), можно определить, является ли эта алгебра алгеброй минимального ранга. Если является, то можно вычислить Fq и найти точное значение для R(Fq [GN ]).

Если она не является алгеброй минимального ранга, то нижняя оценка 2N Fq остается справедливой, тогда как о верхней оценке уже ничего сказать нельзя. Однако, удается доказать, что билинейная сложность умножения в алгебре Fq [GN ] растет линейно относительно её размерности.

Теорема 6. Пусть F[GN ] групповая алгебра абелевой группы порядка N над произвольным полем характеристики p, GN Gl. Тогда существует константа Cl, зависящая только от множества Gl, такая, что Gln \ Gln 1, |Gn | при n, и sup ln = l <. Из теоремы 6 следует, что над произвольным полем F характеристики p верно, что R(F[Gn ]) C · dimF[Gn ], где константа C не зависит от n. При этом, остается открытым вопрос о том, как растет билинейная сложность R(F[Gn ]) при n, если sup ln =. Для доказательства некоторой нетривиальной нижней оценки для такой последовательности групповых алгебр над произвольным полем простой характеристики в диссертационной работе используется следующая теорема14 :

Теорема 7. Пусть A ассоциативная алгебра. Для всех m, n > 0, C(A) dim A + dim(radA)m + dim(radA)n dim(radA)n+m1.

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

Теорема 8. Пусть F[Gn ] последовательность групповых алгебр над полем F характеристики p такая, что Gn Gn \ Gn1, и dim F[Gn ] = pkn.

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

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

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

Одной из мотиваций этих работ являлось найти сложность умножения матриц малого порядка. Давно известно, что алгебра k 22 алгебра матриц размерности 2 2, является алгеброй минимального ранга. Долгое время открытой проблемой было определить, является ли алгебра k 33 алгеброй минимального ранга15. Один способ решения этой задачи описать все Markus Blser. Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. Institut fr Theoretische Informatik, Germany.

P. Brgisser, M. Clausen, M. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.

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

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

Теорема 9 (М. Блезер). Алгебра A над полем k является алгеброй минимального ранга тогда и только тогда, когда где C1,..., Cs локальные алгебры минимального ранга, для которых dim(C /radC ) 2, то есть C k[X]/(p (X)d ) для некоторого неприводимого над k полинома p, degp 2, d 1 и #k 2 dim C 2, = 1,..., s, а B сверхосновная алгебра минимального ранга над k. Сверхосновная алгебра B является алгеброй минимального ранга тогда и только тогда, когда найдутся такие w1,..., wm radB, wi = 0, wi wj = 0, i = j, 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.

S. Winograd. On multiplication in algebraic extension elds. Theoret. Comput. Sci., 8:359–377, 1979.

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

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

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.

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

Markus Blser. A Complete Characterization of the Algebras of Minimal Bilinear Complexity. SIAM J.

Comput., 34(2):277-298, 2004.

что и #k 2N (B) 2, где LB и RB суть правый и левый аннигиляторы radB (то есть множество всех таких x radB, что x(radB) = {0}, соответственно (radB)x = {0}), а N (B) наибольшее целое j, для коj торого (radB) = {0}. Любое из чисел s, u может равняться нулю, а множитель B является необязательным.

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

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

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

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

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

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

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

Ephraim Feig. On systems of bilinear forms whose minimal division-free algorithms are all bilinear. J.

Algorithms 2(3): 261–281, 1981.

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

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

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

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

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

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

Теорема 15. Пусть A локальная или сверхосновная алгебра минимальной мультипликативной сложности. Тогда любой оптимальный квадратичный алгоритм = (f1, g1, w1,..., f, g, w ) для A является почти билинейным. В частности, если w LA RA для всех, то является билинейным.

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

Пример 1. Пусть k поле характеристики отличной от двух. Алгебра k[X]/(X ) является локальной и сверхосновной, но имеет квадратичный алгоритм, который не является билинейным (но естественно является почти билинейным): мы можем вычислить коэффициенты (a + bX)(a + b X) как aa и ab + ba = 2 (b + b )(a + a ) + 1 (b b )(a + a ). Заметим, что X Lk[X]/(X 2 ) = Rk[X]/(X 2 ).

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

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

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

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

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

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

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

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

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

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

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