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

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

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

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

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

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

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

Москва - 2008

00344Э

003449188

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

Научный руководитель

Официальные оппоненты

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

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

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

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

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

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

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени M В Ломоносова http //www eme msu ru в разделе «Наука» - «Работа диссертационных советов» - «Д 501 001 44»

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

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

Трифонов H П

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

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

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

п

а*аз ~ ^ ауа"> 1 < г, ; < п 1/=1

Нетрудно видеть, что для умножения двух векторов

п п

^Да, и

»=1 3-1

где Д и ¡З'3 — числа из к, являющиеся координатами векторов-множителей в базисе а, по определенным выше формулам необходимо выполнить п2 операций умножения переменных из к и п2 — п операций сложения Для многих важных алгебр, таких как алгебра многочленов и алгебра

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

В 1962 году А А Карацуба и Ю П Офман предложили алгоритм умножения чисел длины п в двоичной системе счисления со сложностью 0(nlogj3) Этот алгоритм легко трансформируется в алгоритм умножения многочленов одного переменного степени п Таким образом, впервые было установлено, что традиционный алгоритм не является оптимальным Предложенный алгоритм использовал технику «разделяй-и-властвуй» и неявно основывался на вычислении и последующей интерполяции многочлена второй степени по трем точкам Более полно этот подход был использован A JI Тоомом в 1963 году, предложившим для любого е > 0 алгоритм умножения чисел длины п в двоичной системе счисления сложности

0(п1+0«),

основанный на алгоритме умножения многочленов степени п той же сложности В 1971 году данный результат был улучшен А Шенхаге и Ф Штрассеном, предложившими алгоритмы сложности

0(п log п log logn)

для умножения многочленов степени п и чисел длины п в двоичной записи Этот алгоритм оставался асимптотически самым быстрым на протяжении 26 лет и был улучшен в 2007 году Мартином Фюрером, предложившим алгоритм сложности

nlogn2°(!og*n>

для умножения чисел длины тг

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

2п — 1

арифметических операций Большинство асимптотически быстрых алгоритмов основаны на дискретном преобразовании Фурье В 1973 году Ж Моргенштерн заметил, что дискретное преобразование Фурье имеет суперлинейную сложность, а именно,

fi(nlogn),

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

0(п log п),

однако до сих пор это утверждение не доказано и не опровергнуто

В 1969 году Ф Штрассен опубликовал алгоритм умножения квадратных матриц порядка п сложности

0(п]о^т)

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

0(п2'375)

для умножения двух квадратных матриц порядка п

Нелинейные нижние оценки сложности умножения матриц отсутствуют В 2002 году Ран Раз доказал нижнюю оценку

fi(n2log п)

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

2п2 — 1

требуемых активных скалярных умножений алгоритма (являющаяся одновременно нижней оценкой числа всех арифметических операций) В

1999 году Маркус Блезер улучшил этот результат, доказав, что умножение матриц требует не менее

5 2 о -п2 - Зп

а

операций умножения чисел Амир Шпилька в 2001 году улучшил этот результат для конечных полей

Зп2 - о(п2) для поля 6^(2)

и

(I + 2(рЗЭ- 1)) п2 ~ °^ ДЛЯ П0ЛЯ

Для малых значений п лучшей на сегодняшний день является оценка

2П2 + П-2 (п> 3),

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

п2

однако до сйх пор это утверждение не доказано и не опровергнуто

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

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

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

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

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

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

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

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

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

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

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

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

Публикации и апробирование. Результаты диссертации докладывались на семинаре мехмата МГУ «Математические вопросы кибернетики» (руководитель — академик РАН О Б Лупанов), на VI Меж-дунарожной конференции «Дискретные модели в теории управляющих

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

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

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

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

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

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

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

G = Z„! ® -®Znm) (1)

где nß ^ 2, ß = 1, ..., т, п\ • • • пт = п Числа ni, пт можно выбрать так, что п^ = pft, где pß — простые числа, а dß > 0 (такие группы Znfi называются примарными^, в этом случае представление (1) единственно с точностью до перестановки множителей

В разделе 1 2 вводятся модель вычисления и постановка задачи Пусть U, V, W — конечномерные линейные пространства над полем k, я <р U х V —► W — билинейное отображение Билинейным вычислением (билинейным алгоритмом) для ip называется такая последовательность

(/il il, wu , fr, 9r, WT), где fp € U*, gp e V*, w», s W, 1 < p < г, что для любых и <E U, VZV

г

<p(u, v) = ]TMU)MV)WP p=1

г называется длиной билинейного вычисления Рангом или билинейной сложностью <р называется длина кратчайшего билинейного вычисления для tp Ранг <р обозначается rk <р

Ранг умножения в алгебре А (являющегося билинейнейным отображением А х А —* А) называется рангом алгебры А и обозначается гкЛ Обобщением билинейного вычисления и ранга является квадратичное вычисление и мультипликативная сложность Квадратичным вычислением (квадратичным алгоритмом) для ср является такая последовательность (/i, gu wh fe, gt, wt), где /д, g\ S (U x V)*, год 6 W, 1 < A ^ £, что для любых и £ U, v &V

i

<p{u, v) = £/a(U) v)g\(u, v)w\

A=1

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

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

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

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

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

С(А)^2 dim А - t(A),

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

Отсюда, в частности, следует, что rk А ^ 2 dim А — t(A) Алгебры, для которых оценка АлдерагШтрассена совпадает с верхней, называются алгебрами минимального ранга

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

Элемент а алгебры А называется обратимым, если существует такой а-1 б А, что аа-1 = а'1 а = е, где е — единица алгебры. Обозначим множество обратимых элементов алгебры А через А* Алгебра Б называется алгеброй с делением, если = Ю \ {0} Алгебра А называется локальной, если фактор-алгебра Л/гасМ является алгеброй с делением, и А называется основной, если А/гъАА является прямым произведением алгебр с делением Будем называть алгебру А над полем к сверхосновной, если Л/гас1 А = к4 для некоторого Ь Очевидно, что любая сверхосновная алгебра является основной

Пусть кп*п — алгебра матриц порядка пхп над полем к

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

А*Схх ■ хСяхк2х2х• -хк2*2хВ,

4 V '

и раз

где С\, ,Се суть локальные алгебры минимального ранга, у которых ¿т(Са/1вАСа) > 2, то есть Са = к[Х]/(ра(Х)л") для некоторого неприводимого над к полинома ра, degpa ^2, д,а ^ 1 и$к ^ 2d.vm.Co - 2, (7 = 1,. , з, а В — сверхосновная алгебра минимального ранга над к В является сверхосновной алгеброй минимального ранга тогда и только тогда, когда найдутся такие и]\, , ыт € гас! В, = 0, г ф ], что

тайВ = 1в + Ви)1В+ ■ + Ви)тВ = Ив + ВмзхВ + ■• + ВютВ

и р > 2И(В) — 2, где и ^ суть правый и левый аннигиляторы га(! В (то есть множество всех таких х £ гас! В, что х(гас! В) — 0, соответственно (таАВ)х = 0,), о АГ(В) — наибольшее целое у, для которого (гас1В)3 Ф {0} Любое из чисел я, и может равняться нулю, а множитель В является необязательным

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

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

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

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

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

Теорема 5. Пусть И — блочная циклическая матрица (блочного) порядка р над произвольным полем Г простой характеристики р, все блоки которой являются квадратнъши матрицами,

( Ао Ах

п = Ах А2 Ао

\Л-1 л<> • ■ Ар—2/

Тогда Б эквивалентна1 матрице Р,

(

.... 5 О

. . О

\ 5 0 .. О/

5 = А0 + • + Ар-1

'В данном случае эквивалентность означает существование невырожденных матриц Р и С?, таких что <1е1Р йеЬС) = 1 п Р = РОС) Первое свойство в данном случае необходимо для того, чтобы определители Л а Р совпадали

Теорема 6. Пусть поле Г имеет характеристику р Определитель циклической матрицы С, где

С =

равен в случае, если р\п,

( ао

\а„_х ао

«П-Д ао

Чп-2/

скЛС = (-1)

1»-ЧМ)

п-\

П

е, е"=1 г=0

Теорема 7. Пусть С — циклическая матрица размера п х п, п = рЧ, гдер\Ь ик > 0, над алгебраически замкнутым полем характеристики Р

/ Со Сг с„_1\ С1 с2 Со

С =

\Cn_i со . Сп-г)

Тогда

с!е^= (-1)

Р<Рк-1) [ Р*(<-1)(«-2)

2 ~ 2

( "-1 \Р П 1>Ч •

Теорема 8. Пусть для каждого а, а = в, ,2, блочная циклическая матрица над полем характеристики р построена из различных матриц ^ = 0, , ца - 1, ^ — рТ° для некоторого натурального Гя, следующим образом

Дг =

'о1г в»;-\D-i~1 ■ ОХ!

При этом матрицы имеют размер 1x1 ^ = 1, п = Тогда

где п — П|=1 Ъ ~ порядок матрицы Д,, а ¿[^ суть различные скалярные элементы 1-го столбца матрицы Бе

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

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

rkF[Z„] = 2 n-t

Попутно устанавливается структура таких алгебр

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

F[Zn] а В*

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

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

А = В1,

где В — алгебра Блезера с B/radB = F, dim Л = pkt, р \t. В этом случае

rk Л = 2 dim A-t

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

Д ~ jpdim А

В этом случае

rkA = dim Л

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

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

Обозначим е(п) = п - 1 [|J

Теорема 12. Для любого п

R[Z„] 3 Re(n) х (ВДДа:2 + 1)) ^ Теорема 13. rkR[Zn] = 3 [^J + е(п)

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

Теорема 14.

3 1

rkR[Zm х Z„] -тп - -е(т)е(п).

¿t Z

Теорема 15.

/ ч / \ „ mn-e(m)e(n)

R[Zm х Zn] s x (ВДДж2 + 1)) 2

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

G = Zn, х х Ъщ

Обозначим e(G) = e(ni) e(n¡)

Теорема 16. Пусть G — абелева группа Тогда

Теорема 17. Пусть G — абелева группа, n—\G\, e(G) = I. Тогда

*Ш[С] = \п-\2е

Пусть — последовательность алгебр над одним и тем же полем

к, причем dim А, — пг и пг-> оо Назовем константой асимптотики

1—>00

сложности величину

С(А) = lim

«—»00 Щ

если данный предел существует

Теорема 18. 1 Пусть {А— последовательность групповых алгебр абелевых групп над С Тогда С(А) = 1

2 Пусть

Со = 2- = т = 1,2.

Для каждого то, т = 0,1,2, , существует такая последовательность групповых алгебр {-А™}^ абелевых групп над К, что для любого т константа асимптотики сложности равна С(Ат) -Ст

3 Пусть {А}^ — произвольная последовательность групповых алгебр абелевых групп над К, для которой существует С {А) Тогда существует т ^ 0 . С{А) = Ст

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

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

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

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

Теорема 19. Пусть pi и р2 — полиномы т переменных Xi, . , Хт степеней dр по переменным Хц, d¡¡, > 0, 1 < ц < т над полем к, содержащим все корни степени М = Yl^i^d^+l) из 1 Пусть также р — характеристика поля к, и М = pdt, где р \ t Тогда существует билинейный алгоритм умножения полиномов р\ и р2 длины 2М — t.

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

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

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

ОД - С2*2 х С2 (2)

Теорема 21, С[5з] является алгеброй минимального ранга Теорема 22. Для сложности умножения в С[5з] выполняется

гкС[5з] = 9

Теорема 23. Алгебра С[5з] содержит единственную подалгебру, изоморфную алгебре матриц

0x2

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

Теорема 24. ОД] = С2х2 х С4

Теорема 25. гкОД] = И

Гипотеза о прямой сумме в теории сложности алгебр гласит, что для любых алгебр А и В над полем к справедливо гкА х В = гк Л + гк В На сегодняшний день эта гипотеза не доказана и не опровергнута

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

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

Теорема 27 Имеет место изоморфизм

С[Л4] = С3 х С3х3,

а также сложностное равенство

гкС[Л4] = гкС3х3 + 3

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

К[Л4] = Ж х ВД/(Х2 + 1) х К3х3,

а также следующая нижняя оценка сложности умножения матриц третьего порядка

гкК3х3 ^ гкМ[Л4] - 4

Теорема 29. Справедливо, по крайней мере, одно из следующих утверждений

1 гкС3*3 < гкК3х3,

2 гкС[>Ц] < гкК[А4],

3 гипотеза о прямой сумме является неверной

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

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

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

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

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

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

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

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

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

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

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

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

6 Поспелов АД О сложности умножения полиномов и матриц Сборник статей молодых ученых факультета ВМиК МГУ, 2008, выпуск №5 Москва, издательский отдел ф-та ВМиК МГУ им М В Ломоносова (2008), с 83-97

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

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 23 09 2008 г Формат 60x90 1/16 Услпечл 1,0 Тираж 100 экз Заказ 514 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к

Введение

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

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

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

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

2 Коммутативные групповые алгебры

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

2.2 Определитель циклической матрицы над алгебраически замкнутым полем

2.3 Ранг умножения в групповых алгебрах циклических групп

2.4 Ранг умножения в групповых алгебрах произвольных абелевых групп.

3 Алгебры над вещественным полем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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