Некоторые вопросы теории сложности билинейных отображений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

Лысиков Владимир Владимирович

Некоторые вопросы теории сложности билинейных отображений

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

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

6 2014

Москва - 2013

005544716

005544716

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

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

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

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

профессор, руководитель отдела теоретической кибернетики ИСП РАН Кузюрин Николай Николаевич

кандидат физико-математических наук, старший разработчик ООО «Яндекс» Поспелов Алексей Дмитриевич

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

университет «МЭИ»

Защита состоится «_Ж_» 201^ г. в I/ часов на заседании

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

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

Автореферат разослан «.

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

Костенко В. А.

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

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

Одной из важных проблем алгебраической теории сложности является задача определения сложности умножения матриц1'2. В 1969 г. был опубликован алгоритм Ф. Штрассена3 для умножения квадратных матриц размера 71 х 71, имеющий сложность 0(nIog27) арифметических операций вместо 0(п3) для тривиального алгоритма, что положило начало исследованиям асимптотически быстрых алгоритмов умножения матриц. После нескольких лет исследований в этой области Д. Копперсмитом и Ш. Виноградом4 был получен алгоритм с асимптотической сложностью 0(п2-376). Недавние исследования с использованием компьютерных средств5'6,7 позволили улучшить эту оценку до 0(п2'373).

Штрассен также заметил связь алгоритмов умножения матриц с алгебра-

1 Алексеев В. В. Сложность умножения матриц. Обзор // Кибернетпч. сборн. — 1988. — Л'* 25. — С. 189-236.

2 Bürgisser Р., Clausen M., Shokrollahi М.А. Algebraic Complexity Theory. — Springer, 1997.

3 Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. — 1969. — Vol. 13, no. 4. — P. 354-356.

1 Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // Journal of symbolic computation. - 1990. - Vol. 9, no. 3. - P. 251-280.

5 Stothers A. J. On the complexity of matrix multiplication : Ph. D. thesis / A.J. Stothers ; University of Edinburgh. — 2010.

6 Vassilevska Williams V. Multiplying matrices faster than Coppersmith-Winograd // Proceedings of the 44th symposium on Theory of Computing / ACM. - 2012. — P. 887-898.

7 Жданович Д. В. Экспонента сложности матричного умножения // Фундаментальная и прикладная математика. - 2012. - Т. 17, № 2. — С. 107-1GG.

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

Определение. Пусть 5 — кольцо, 1/,У,Ш — конечномерные свободные модули над Б к <р: V х V -5- ТУ — билинейное отображение. Билинейным алгоритмом для <р называется последовательность (/ъ <7ъ /2,52,22;...; /г, 9г, где € и*, д$ € V*, г3 е Ш, такая, что для любых х € и, у £ У выполняется

Количество троек г называется сложностью билинейного алгоритма. Билинейной сложностью или рангом отображения <р называется минимально возможная сложность билинейного алгоритма для этого отображения. Ранг отображения <р обозначается R(<p).

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

В 1981 г. А. Алдером и Ф. Штрассеном8 была получена нижняя оценка

8 Alder A., Strassen V. On the Algorithmic Complexity of Associative Algebras /,/ Theor. Comput. Sri — 1981. - Vol. 15.- P. 201-211.

г

сложности умножения в алгебрах в терминах их структуры.

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

R(Ä) > 2 dim A-t(A), где t(Ä) — количество максимальных двусторонних идеалов алгебры А.

Эта оценка оказалась неулучшаемой, в связи с чем возник вопрос об описании всех алгебр, на которых она достигается — алгебр минимального ранга. Эта задача решалась несколько десятков лет многими исследователями, окончательное описание было получено М. Блезером9. Одним из ключевых элементов этого описания являются улучшенные нижние оценки сложности умножения в алгебрах матриц10'11.

Теорема (М. Блезер). Пусть D — алгебра с делением, п ^ 2, А = Dnyn — простая алгебра. Тогда

R(A) > ^dimA-3n.

Теорема (М. Блезер). Для ранга алгебры матриц размера 3x3 над произ-влънъш полел1 F справедлива оценка

R(F3*3) > 19.

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

9 Blaser M. A Complete Characterization of the Algebras of Minimal Bilinear Complexity // SIAM J. Comput. — 2004. — Vol. 34, no. 2. — P. 277-298.

10 Blaser M. Beyond the Alder-Strassen bound // Theor. Comput. Sei. - 2005.- Vol. 331, no. 1.— P. 3-21.

11 Bläser M. On the complexity of the multiplication of matrices of small formats // J. Complexity.— 2003. - Vol. 19, no. 1. - P. 43-00.

12 Bläser M., de Voltaire A.M. Semisimple algebras of almost minimal rank over the reals // Theor. Comput. Sei. — 2009. — Vol. 410, no. 50. — P. 5202-5214.

Теорема (М. Блезер, А. М. де Вольтер). Любая полупростая алгебра почти минимального ранга над М имеет вид

А = И х М2х2 х • • • х R2*2 хСх---хСхМх---хМ.

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

Блезером и де Вольтером были отмечены несколько ключевых проблем на пути к этому обобщению. Одним из ключевых вопросов на пути к описанию алгебр почти минимального ранга является вопрос о билинейной сложности умножения обобщенных кватернионов. Оптимальный алгоритм умножения кватернионов над полем действительных чисел был получен в 70х годах13'14,15, однако он не обобщается непосредственным образом на алгебры обобщенных кватернионов над произвольным полем. В диссертации получен критерий почти минимальности для класса локальных алгебр, позволяющий получить оптимальный алгоритм в общем случае.

Для рассмотрения другого проблемного случая необходимо улучшить упомянутую выше нижнюю оценку М. Блезера для сложности умножения в простых алгебрах. Несмотря на то, что методы, использованные М. Лэндсбергом16 позволяют получить оценку, более сильную асимптотически (порядка 3п2), они неприменимы для алгебр малой размерности. В данной работе оценка Блезера улучшается на единицу для матричных алгебр над расширениями основного поля.

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

13 De Groote Н. F. On the complexity of quaternion multiplication // Information Processing Letters. — 1975. - Vol. 3, no. 6. - P. 177-179.

14 Howell T. D, Lafon J.-C. The complexity of the quaternion product // Coniell University Tech. Rep. —

1975.

15 Brockett R. W., Dobkin D. On the optimal evaluation of a set of bilinear forms // Linear Algebra and Its Applications. — 1978. - Vol. 19, по. 3. — P. 207-235.

18 Landsberg J. M. New lower bounds for the rank of matrix multiplication // Preprint, ArXiv:1206.1530. —

2012.

полями различных характеристик. Т. Д. Хауэлл17 первым отметил, что билинейная сложность отображения не возрастает при расширении кольца, над которым рассматриваются алгоритмы, а также доказал, что в некоторых условиях такое расширение не влияет на сложность, в частности, что минимальная сложность достигается при использовании в качестве основного кольца алгебраически замкнутого поля. А. Шёнхаге18 рассматривал сложность матричного умножения над различными полями одной характеристики. Он доказал, что асимптотика сложности матричного умножения над полями одной характеристики одинакова с точностью до постоянного множителя. Штрассен19 показал, что этот множитель не превосходит 4 при выполнении гипотезы Штрассена о прямой сумме.

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

Цель работы: описание структуры различных классов алгебр почти минимального ранга; исследование билинейной сложности Z-билинейных отображений над различными полями.

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

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

Основные результаты:

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

17 Howell Т. D. Global properties of tensor rank /'/' Linear Algebra and its Applications.— 1978.— Vol. 22. - P. 9-23.

18 Schonhage A. Partial and total matrix multiplication // SIAM J. Comput. — 1981. —Vol. 10, no. 3.— P. 434-455.

19 Strassen V. Relative bilinear complexity and matrix multiplication. // Journal fiir die reine und angewandte Mathematik. — 1987. — Vol. 375. — P. 406-443.

2. Получен критерий почти минимальности ранга для локальных алгебр.

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

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

5. Полностью описана структура полупростых алгебр почти минимального ранга над бесконечным полем характеристики, отличной от 2.

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

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

Публикации. По теме диссертации опубликовано 5 работ, среди них 2 работы [2, 4] в рецензируемых изданиях, включенных в перечень ВАК.

Апробация результатов. Результаты диссертации докладывались на следующих семинарах и конференциях:

— на семинаре «Дискретные функции и сложность алгоритмов» под руководством В. Б. Алексеева, С. С. Марченкова и А. А. Вороненко (кафедра математической кибернетики ВМК МГУ) в 2011-13 гг.;

— на XI международном семинаре «Дискретная математика и ее приложения» (Москва, 18-23 июня 2012);

— на международной конференции «Мальцевские чтения» (Новосибирск, 12-16 ноября 2012);

— на семинаре «Дискретная математика и математическая кибернетика» под руководством В. Б. Алексеева, А. А. Сапоженко и С. А. Ложкина (кафедра математической кибернетики ВМК МГУ) в 2012-13 гг.:

— на международном молодежном научном форуме «Ломоносов-2013»;

Структура и объем диссертации. Работа состоит из введения, четырех глав и списка литературы, содержащего 41 наименование. Диссертация содержит 73 страницы и включает 1 таблицу.

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

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

В главе 1 приводятся основные определения и известные факты, касающиеся билинейных отображений, алгебр и билинейной сложности. В разделе 1.1 приводятся определения билинейного отображения и алгебры. В разделе 1.2 рассматриваются основные понятия теории конечномерных ассоциативных алгебр. В разделе 1.3 вводится рассматриваемая модель вычислений — модель билинейных алгоритмов — и приводятся простейшие оценки сложности билинейных алгоритмов. В разделе 1.4 приводится определение и основные свойства тензорного произведения.

В главе 2 рассматриваются билинейные отображения малого ранга и алгоритмы умножения кватернионов.

В разделе 2.1 вводится понятие алгебры обобщенных кватернионов и описывается их структура.

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

Определение 2.4. Билинейный алгоритм (/i, gi, z\;...; /г, gr, zr) будем называть двухкомпонентным, если множество индексов {1,.. .,г} можно разбить на непересекающиеся множества I и ,7 такие, что {/¿¡г 6 /} и {<?jjj 6 J} являются базисами пространств U* и У* соответственно.

Лемма 2.1. [2] Пусть F — поле, U, V, W — векторные пространтева над F, иср: U xV-^W — билинейное отоборажение. Если R{<p) = dim U + dim V, lker <p — 0, и в любом базисе пространства U найдется <р-регулярный элемент, то любой оптимальный билинейный алгоритм для <р является двухкомпонентным.

Теорема 2.4. [2] Пусть F — поле, U, V, W — векторные пространтсва над F,u<p:UxV->W — билинейное отоборажение. Двухкомпонентный

билинейный алгоритм для <р существует тогда и только тогда, когда существуют базисы щ,..., ит и v\,..., vn пространств U и V соответственно, и наборы z[,..., z!m и z'{,... элементов W такие, что

<р(щ, vj) = Aijz'i + Hijz" для некоторых коэффициентов € F.

Теорема 2.6. [2] Пусть F — поле, А — локальная алгебра над F, dim А =п. Если А не является алгеброй минимального ранга, то есть R(A) ^ 2п, то А имеет почти минимальный ранг тогда и только тогда, когда в А существует пара базисов щ = 1, it2,..., ип и vi = 1, i>2,..., vn и пара наборов элементов ..., z'n и т![,..., г" такие, что

UiVj = А ^ + lJ-ijz"

для некоторых £ F.

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

Теорема 2.7. [2] Пусть F — поле, char F ^ 2, Н — алгебра обобщенных кватернионов с делением над F. Тогда R(H) = 8.

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

Теорема 2.8. [2] Пусть F — поле. Если и По - алгебры обобщенных кватернионов с делением над F, а А = Н\Х Hi, то R(A) = 16.

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

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

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

Теорема 3.5. [2] Пусть К — расширение бесконечного поля F, п ^ 2, А = Кпхл. Тогда

Rf(A) ^ ^dimfyl-3n+l.

Теорема 3.6. [2] Любая полупростая алгебра почти минимального ранга над бесконечным полем F, char F ф 2, имеет вид II или Н х В, где Н — алгебра обобщенных кватернионов с делением, В полупростая алгебра минимального ранга.

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

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

В разделах 4.2 и 4.3 приводятся два разных доказательства основного результата главы. Доказано, что ранг Z-билинейного отображения над алгебраически замкнутым полем характеристики 0, равен рангу этого отображения над всеми алгебраически замкнутыми полями простых характеристик, за исключением конечного числа.

Теорема 4.1. [4] Для любого Z-билинейного отображения </? справедливо соотношение

ДоЫ = пф)

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

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

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

1. Лысиков В. В. О билинейных алгоритмах умножения обобщенных кватернионов // Материалы XI международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения О. Б. Лупанова / М.: МГУ. - 2012. - С. 141-143.

2. Лысиков В. В. Об алгебрах почти минимального ранга // Дискретная математика. — 2012. — Т. 24, № 4. — С. 3-18.

3. Лысиков В. В. Сложность умножения матриц над полями различной характеристики // Международная конференция «Мальцевские чтения», 12-16 ноября 2012 г. Тезисы докладов / Новосибирск: Институт математики им. С. Л. Соболева, Новосибирский государственный университет. — 2012. - С. 41.

4. Лысиков В. В. О билинейных алгоритмах над полями различных характеристик // Вестник Московского Университета. Серия 15: Вычислительная математика и механика. — 2013. — Т. 4. — С. 33-38.

5. Лысиков В. В. О целочисленных билинейных отображениях // Материалы Международного молодежного научного форума «Ломоносов-2013» [Электронный ресурс] / М.: МАКС Пресс. — 2013.

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

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

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

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

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

04201455897 Лысиков Владимир Владимирович

Некоторые вопросы теории сложности билинейных отображений

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

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

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

Москва - 2013

Содержание

Введение ............................................................4

Глава 1. Основные понятия....................................13

1.1. Билинейные отображения и алгебры....................13

1.2. Ассоциативные алгебры над полем ......................19

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

1.4. Тензорные произведения и расширение кольца скаляров 29

Глава 2. Алгоритмы умножения обобщенных кватернионов ................................................................34

2.1. Алгебры обобщенных кватернионов......................34

2.2. Билинейные отображения малого ранга..................36

2.3. Сложность умножения обобщенных кватернионов ... 41

2.4. Ранг произведения алгебр обобщенных кватернионов . 42

Глава 3. Полу простые алгебры почти минимального

ранга..............................................................47

3.1. Следствия известных оценок..............................47

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

Глава 4. Целочисленные билинейные отображения над

полями различных характеристик........................59

4.1. Ненулевые тензорные произведения......................59

4.2. Связь между билинейными алгоритмами................61

4.3. Метаматематическое доказательство ....................65

«Литература..........................................................68

Введение

Теория сложности вычислений является одной из важнейших областей математической кибернетики. После появления компьютеров измерение эффективности используемых алгоритмов и исследование возможностей их улучшения стали важными практическими вопросами, изучение которых привело, в том числе, к появлению математической теории, в рамках которой исследуется различные характеристики эффективности алгоритмов в различных математических моделях вычислений. Наиболее важные из таких характеристик — это время работы алгоритма, т. е. количество элементарных шагов в рассматриваемой модели, и используемая память. Появление теории сложности вычислений можно отнести к пятидесятым годам XX века: Б. А. Трахтенброт в [30] утверждает, что исследования временной сложности алгоритмов в СССР начались в 1956 г., а М. Сипсер в [25] упоминает письмо К. Гёделя к Дж. фон Нейману, датируемое 1953 г. В настоящее время теория сложности вычислений является очень широкой областью исследований, включающей множество направлений и связанной практически со всеми областями математики.

Одним из направлений в теории сложности вычислений является алгебраическая теория сложности. Естественно, что алгоритмы, вычисляющие функции, связанные с какой-либо алгебраической струк-

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

Одной из основных проблем алгебраической теории сложности является задача определения сложности умножения матриц. В 1969 г. был опубликован алгоритм Ф. Штрассена [27] для умножения квадратных матриц размера п х п, имеющий сложность 0(п1о®27) арифметических операций вместо 0(п3) для тривиального алгоритма, что положило начало исследованиям асимптотически быстрых алгоритмов умножения матриц. Штрассен также заметил связь алгоритмов умножения матриц с алгебраическим понятием тензорного ранга, что позволило применять для изучения сложности этих алгоритмов конструкции мультилинейной алгебры. После нескольких лет исследований в этой области Д. Копперсмитом и Ш. Виноградом [12] был получен алгоритм с асимптотической сложностью 0(п2-376). Недавние исследования с использованием компьютерных средств [26, 31, 36]

позволили улучшить эту оценку до 0(п2'373). Наилучшая известная на текущее время нижняя оценка сложности умножения квадратных матриц 3п2 — о(п2) была получена М. Лэндсбергом [18]. В случае, если в алгоритме разрешается использовать только ограниченные по модулю некоторой фиксированной константой коэффициенты, известна оценка вида Q,(n2\ogn) [22]. Подробные обзоры истории верхних оценок сложности матричного умножения и применяемых для их получения методов содержатся в [32] и [5].

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

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

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

В 1981 г. А. Алдером и Ф. Штрассеном [1] была получена нижняя оценка сложности умножения в алгебрах в терминах их структуры. Эта оценка оказалась неулучшаемой, в связи с чем возник вопрос об описании всех алгебр, на которых она достигается — алгебр минимального ранга и минимальной мультипликативной сложности. Эта задача решалась несколько десятков лет многими исследователями, окончательное описание было получено М. Блезером [3] для ранга и М. Блезером и Б. В. Чокаевым [6] для мультипликативной сложности. После этого в [7] М. Блезером и А. М. де Вольтером было начато изучение алгебр почти минимального ранга, т. е. алгебр, для которых билинейная сложность на 1 больше оценки Алдера-Штрассена. Одной из целей данной диссертации является продолжение этих исследо-

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

Для классификации полупростых алгебр почти минимального ранга были получены результаты, которые могут представлять самостоятельную ценность. Так, было получено точное значение сложности умножения обобщенных кватернионов. Оптимальный алгоритм умножения кватернионов над полем действительных чисел был получен в 70х годах [10, 13, 16], однако он не обобщается непосредственным образом на алгебры обобщенных кватернионов над произвольным полем. Задача об определении сложности умножения обобщенных кватернионов была отмечена в [7] как один из ключевых вопросов на пути к описанию алгебр почти минимального ранга.

Также была улучшена на единицу нижняя оценка Блезера для сложности умножения в матричных алгебрах [4]. Несмотря на то, что методы, использованные М. Лэндсбергом в [18] позволяют получить оценку, более сильную асимптотически, наш результат дает лучшую оценку для алгебр малой размерности.

Другой целью диссертации является исследование связи между алгоритмами вычисления билинейного отображения с целыми ко-

эффициентами (например, умножения матриц или полиномов) над полями различных характеристик. Мы докажем равенство рангов билинейного отображения с целочисленными коэффициентами над алгебраическими замкнутыми полями нулевой и простой характеристики, за исключением конечного числа простых характеристик. Ранее результаты, касающиеся связи сложности одного и того же билинейного отображения над различными кольцами и полями, были получены в [15] и [24]. Т. Д. Хауэлл первым отметил, что билинейная сложность отображения не возрастает при расширении кольца, над которым рассматриваются алгоритмы, а также доказал, что в некоторых условиях такое расширение не влияет на сложность, в частности, что минимальная сложность достигается при использовании в качестве основного кольца алгебраически замкнутого поля. А. Шёнхаге рассматривал сложность матричного умножения над различными полями одной характеристики. Он доказал, что асимптотика сложности матричного умножения над полями одной характеристики одинакова с точностью до постоянного множителя. Штрассен в [29] показал, что этот множитель не превосходит 4 при выполнении гипотезы Штрассена о прямой сумме.

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

В главе 1 приводятся основные определения и известные факты, касающиеся билинейных отображений, алгебр и билинейной сложности.

В главе 2 рассматриваются билинейные отображения малого ранга и алгоритмы умножения кватернионов.

В разделе 2.1 вводится понятие алгебры обобщенных кватернионов.

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

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

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

Глава 3 посвящена классификации полупростых алгебр пояти минимального ранга над бесконечным полем характеристики, отличной

от 2.

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

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

В главе 4 рассматривается связь значений ранга Z-билинeйнoгo отображения над полями различных характеристик.

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

В разделах 4.2 и 4.3 приводятся два разных доказательства основного результата главы, использующие различные методы. Доказано, что ранг Z-билинeйнoгo отображения над алгебраически замкнутым полем характеристики 0, равен рангу этого отображения над всеми алгебраически замкнутыми полями простых характеристик, за исключением конечного числа.

Основные результаты диссертации

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

2. Получен критерий почти минимальности ранга для локальных алгебр.

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

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

5. Полностью описана структура полу простых алгебр почти минимального ранга над бесконечным полем характеристики, отличной от 2.

6. Установлено, что значения ранга Z-билинeйнoгo отображения над алгебраически замкнутыми полями различных характеристик совпадают за исключением конечного числа простых характеристик.

Глава 1 Основные понятия

1.1. Билинейные отображения и алгебры

Обычно в литературе по алгебраической теории сложности рассматриваются билинейные отображения векторных пространств над полем, но нам потребуется более общее определение, работающее над коммутативным кольцом, рассмотриваемое, например, в [15]. Аналогом понятия векторного пространства в этом случае является понятие модуля над кольцом (см. напр. [19, 34]).

Термин «кольцо» всюду в диссертации будет обозначать коммутативное кольцо с единицей.

Определение 1.1. Пусть Я — кольцо. Модулем над 51 называется абелева группа (М, +) с операцией умножения на элементы кольца 5", удовлетворяющей соотношениям

а(х + у) = ах + ау, (а + Ъ)х — ах + Ьх, а(Ъх) = (аЬ)х, 1 • х = х

для любых а,Ь Е в, х,у £ М.

Кольцо Б называют кольцом скаляров модуля М, а его элементы — скалярами.

Обычным образом вводятся понятия гомоморфизма, изоморфизма, подмодуля и прямой суммы модулей.

Определение 1.2. Пусть Б — кольцо, М и N — модули над в. Отображение р: М N называется гомоморфизмом модулей, если оно сохраняет операции сложения и умножения на скаляры из т. е.

4>{х + у) = <р(х) + (р(у), (р(ах) = сир(х)

для любых а € Б, х,у € М.

Гомоморфизм, являющийся взаимно-однозначным отображением, называется изоморфизмом.

В случае, когда <5 — поле, гомоморфизмы модулей суть линейные операторы, а изоморфизмы — обратимые линейные операторы.

Определение 1.3. Подмножество N модуля М называется подмодулем, если оно замкнуто относительно операций сложения и умножения на скаляры, т.е. для любых щ, п^ Е N и а € Б сумма щ + пч и произведение ащ также принадлежат N.

Определение 1.4. Пусть 5 — кольцо, М и N — модули над 5. Прямой суммой модулей М и N называется модуль МфА7", состоящий

из пар вида (х, у), где х 6 М, у £ N, с покоординатным сложением и умножением.

Из определения видно, что любое кольцо Э может рассматриваться как модуль над собой. С помощью прямых сумм можно определить модуль »9п = ,9®,9ф---©»9, элементами которого являются наборы

п раз

длины п, составленные из элементов »9. Под <9° удобно понимать тривиальный модуль 0, состоящий из единственного элемента — нуля. Модули вида Бп наиболее близки по свойствам конечномерным векторным пространствам над полем, например, в них можно корректно ввести обобщения понятий базиса и линейной зависимости.

Определение 1.5. Пусть Б — кольцо. Модуль М над Б будем называть конечномерным свободным модулем, если М = Б71 для некоторого п ^ 0. Число п будем называть размерностьюI" свободного модуля М.

Определение 1.6. Пусть Б — кольцо, М — модуль над Б. Гомоморфизмы /: М Б будем называть линейными функционалами на М. Множество М* всех линейных функционалов можно рассматривать

^ Обычно в алгебре эту величину называют рангом свободного модуля, но мы используем термин «ранг» в другом смысле.

как модуль над «9, если определить операции следующим образом:

для любых /, д Е М*, х Е М, а Е 5. Модуль М* называется сопряженным к М.

Перечислим простейшие свойства конечномерных свободных модулей, которые обобщают аналогичные свойства конечномерных линейных пространств.

Утверждение 1.1 ([19, §111.6]). Пусть Б — кольцо, М — конечномерный свободный модуль над Б. Справедливы следующие утверждения:

1. В М существует базис, то есть набор элементов е\,...,еп такой, что любой элемент х Е М представляется в виде

единственным образом. Количество элементов в базисе равно размерности М.

2. Сопряэюенный модуль М* также является конечномерным свободным модулем, его размерность совпадает с размерностью М.

(1 + 9)(х) = №+д(х) (а/) (х) = а • ¡(х)

п

г=1

3. Если е\,..., еп — базис М, то существуют линейные функционалы £1,... ,еп е М*, удовлетворяющие соотношению

£г(ез) = ^гз-

Эти функционалы образуют базис М*, называемый сопряженным к базису е\,... еп. 4■ Любой линейный функционал / е М* имеет вид

п п

/СУ ^ = ^ ^ ^г/г;

г=1 г=1

где /■ = /(а).

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

Определение 1.7. Пусть 5 — кольцо, II, V, — модули над 5. Отображение <р: II х V IV называется билинейным, если выполняются соотношения

<¿>(012:1 + а2х2, у) = а!</?(ж1, г/) + а2р(х2, у), 012/1 + а2у2) = 2/1) + а2<р{%5 2/2)

для любых аь а2 € ж, жь £ £Л У> 2/1> 2/2 € V.

В случае, если из контекста не ясно, какое кольцо 5 рассматривается, мы будем использовать термин «б'-билинейное отображение».

Если С/, У, И7 — конечномерные свободные модули, то для того, чтобы однозначно задать билинейное отображение <£>, достаточно определить его значения на