Точные нижние оценки для алгебраических проблемНИР

Соисполнители НИР

МГУ имени М.В.Ломоносова Координатор

Источник финансирования НИР

грант РФФИ

Этапы НИР

# Сроки Название
1 17 мая 2012 г.-31 декабря 2012 г. Точные нижние оценки для алгебраических проблем
Результаты этапа:
2 1 января 2013 г.-31 декабря 2013 г. Точные нижние оценки для алгебраических проблем
Результаты этапа:
3 1 января 2014 г.-31 декабря 2014 г. Точные нижние оценки для алгебраических проблем
Результаты этапа: Одной из фундаментальных оценок в теории билинейной сложности является нижняя оценка Алдера-Штрассена для ранга ассоциативных алгебр: $R(A) \geq 2 \dim A – t(A)$, где t(A) – количество максимальных двусторонних идеалов в алгебре A. После того, как М. Блезером (руководитель германской части нашего совместного проекта) были описаны все алгебры, для которых эта оценка достигается (алгебры минимального ранга), естественно исследовать вопрос об описании алгебр, ранг которых превышает эту оценку на 1 (алгебр почти минимального ранга). Нами получено полное описание полупростых алгебр над полем отличной от 2 характеристики, обладающих этим свойством. А именно, доказано, что полупростая алгебра почти минимального ранга над таким полем имеет вид Q х B, где Q – алгебра обобщенных кватернионов, а B – алгебра минимального ранга. В частности, установлено, что ранг алгебры обобщенных кватернионов равен 8. Некоторые результаты, использованные в доказательстве этой теоремы, представляют самостоятельный интерес. Был получен критерий почти минимальности ранга для класса локальных алгебр в терминах существования особым образом связанных базисов. С помощью применения этого критерия была доказана почти минимальность алгебр обобщенных кватернионов. Также, для доказательства того, что некоторые простые алгебры не являются алгебрами почти минимального ранга, была улучшена нижняя оценка М. Блезера для ранга простых алгебр $R(D^{n\times n}) \geq 2.5 \dim D^{n\times n} – 3n$ в частном случае, когда $D$ является расширением основного поля (здесь $D^{n\times n}$ - алгебра квадратных матриц порядка $n$ над $D$). Знание точного значения ранга алгебр обобщенных кватернионов позволяет исследовать более тонкие вопросы о свойствах оптимальных билинейных алгоритмов для умножения в таких алгебрах. Де Гроотом было введено отношение эквивалентности на множестве всех билинейных алгоритмов умножения в некоторой алгебре. Два билинейных алгоритма называются эквивалентными, если они получаются друг из друга линейными преобразованиями пространств аргументов и результата, сохраняющим билинейное отображение, вычисляемое алгоритмом. Доказано, что для умножения обобщенных кватернионов существует бесконечно много попарно неэквивалентных оптимальных билинейных алгоритмов. Используемые для изучения алгебр почти минимального ранга конфигурации базисов могут быть обобщены для изучения структуры произвольных тензоров, ранг которых не превышает суммы двух размерностей, и билинейных алгоритмов для их вычисления. С помощью этих обобщенных базисов был получен критерий почти минимальности для сверхосновных алгебр и получены нижние оценки для конкретных тензоров: 12 для ранга умножения комплексных матриц формата <2,2,1> над полем действительных чисел, и 16 для умножения кватерниона на пару кватернионов. Доказано, что локальные алгебры, соответствующие идеалам из одной из неприводимых компонент точечного многообразия Гильберта, являются алгебрами минимального ранга, и тензоры умножения в этих алгебрах обладают структурой, позволяющей им быть использованными в конструкции Копперсмита-Винограда для построения асимптотически быстрых алгоритмов умножения матриц. Была исследована билинейная сложность задачи умножения матрицы размера 5 x 2 на матрицу размера 2 x 2. Для этой задачи известен (J. E. Hopcroft и L. R. Kerr) билинейный алгоритм со сложностью 18. В то же время для той же задачи построен приближенный билинейный алгоритм со сложностью 16 [Алексеев В.Б., Смирнов А.В. О точной и приближенной билинейных сложностях умножения матриц размеров 4 × 2 и 2 × 2 // Современные проблемы математики, вып. 17, 2013, с. 135-152]. В работе по проекту для билинейной сложности задачи умножения матрицы размера 5 x 2 на матрицу размера 2 x 2 удалось получить нижнюю оценку 17 над любым полем. Из двойственности для задач умножения матриц получаем, что билинейная сложность задач <2,5,2> и <2,2,5> также не меньше 17 над любым полем. Этим показано, что точная билинейная сложность и приближенная билинейная сложность в этих задачах различаются над любым полем. Для усиления нижней оценки изучалась возможность существования решения со сложностью 17. Множество всех возможных (гипотетически) решений разбито на 3 класса. Для двух из них полностью доказана невозможность. Третий класс предстоит дополнительно исследовать. Большое внимание было уделено компьютерному поиску новых, практически более быстрых алгоритмов перемножения матриц малой размерности. Был разработан алгоритм, позволяющий “автоматически” строить функциональные приближенные решения из численных приближенных решений при некоторых предположениях. С помощью этого алгоритма были “автоматически” найдены функциональные приближенные решения с минимальной известной сложностью для всех задач < m,n,p > с условием m*n*p<=30 (кроме <2,2,7>). Большинство из этих результатов были ранее получены А.В. Смирновым с использованием в каждом случае специального подбора. С помощью разработанного алгоритма был найден приближенный алгоритм перемножения матриц для задачи <2,2,6> сложности 19 (ранее был известен приближенный алгоритм для этой задачи сложности 20).

Прикрепленные к НИР результаты

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