![]() |
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Одной из важных проблем является ускорение вычислений. Это достигается как за счет создания новой вычислительной техники, так и за счет поиска новых быстрых алгоритмов для вычислений. Еще в 1960-х годах было обнаружено, что стандартные алгоритмы умножения чисел (“в столбик”) и матриц (“строка на столбец”) не являются асимптотически оптимальными. И если для умножения чисел довольно быстро были найдены почти оптимальные (асимптотически) алгоритмы, то для умножения матриц задача оказалась намного сложнее. Поиск быстрых алгоритмов умножения матриц в настоящее время является частью более общей проблемы – исследования сложности умножения в произвольных алгебрах. Проект направлен на исследование возможности существования быстрых алгоритмов для некоторых конкретных алгебраических вычислений, в частности для умножения матриц и обобщенных кватернионов , на описание алгебр, сложность умножения в которых достигает (или почти достигает) известных нижних оценок.
Проведены исследования, связанные с получением нижних оценок сложности умножения в различных алгебрах, описанием свойств алгебр, в которых достигаются или почти достигаются известные нижние оценки, с поиском быстрых алгебраических алгоритмов и их применением. Получен критерий почти минимальности ранга для локальных алгебр, описана структура полупростых алгебр почти минимального ранга над полями отличной от 2 характеристики. Доказано существование бесконечного количества классов эквивалентности (относительно преобразований де Гроота) для билинейных алгоритмов умножения обобщенных кватернионов. Обобщено понятие M-базисов на произвольные тензоры, ранг которых не превосходит суммы двух размерностей. Получено описание одного класса тензоров, которые могут быть использованы как базовые в схеме Копперсмита-Винограда. Доказано, что ранг билинейного отображения с целочисленными коэффициентами одинаков над алгебраически замкнутыми полями различных характеристик, за исключением конечного числа простых характеристик. Доказано, что произвольная алгебра является алгеброй минимальной мультипликативной сложности тогда и только тогда, когда она является алгеброй минимального ранга. Для сверхосновных и локальных алгебр минимальной мультипликативной сложности доказано, что все квадратичные алгоритмы для таких алгебр являются почти билинейными в некотором смысле. Доказано, что локальные алгебры из специального класса алгебр над конечными полями однозначно определяются размерностью алгебры и размерностью ее радикала. Таким образом, установлены классы изоморфизмов локальных алгебр специального вида над конечными полями. Доказано, что над произвольным полем билинейная сложность задачи умножения матрицы размера 4х2 на матрицу размера 2х2 равна 14, а задачи умножения матрицы размера 5х2 на матрицу размера 2х2 не меньше 17. Построен приближенный алгоритм сложности 19 для перемножения матриц размеров 6 х 2 и 2 х 2. Получен быстрый способ преобразования схем из функциональных элементов над конечными полями в безопасные относительно атак типа чтения ограниченного числа переменных аналоги. Для этого разработан новый подход к получению быстрых алгоритмов умножения полиномов над произвольными полями положительной характеристики и верхних оценок для алгоритмов, основанных на дискретном преобразовании Фурье, обеспечивающий безопасность при чтении ограниченного числа промежуточных результатов. Получены достаточные алгебраические условия на поле для того, чтобы существовал алгоритм умножения многочленов над ним сложности меньшего порядка, чем n log(n) log log(n) для умножения двух многочленов степени n. Также получены необходимые условия того, что модель алгоритмов, основанных на эмуляции дискретных преобразований Фурье над кольцами, не позволяет получить алгоритмы быстрее алгоритмов Шёнхаге-Штрассена и Кантора-Калтофена.
МГУ имени М.В.Ломоносова | Координатор |
грант РФФИ |
# | Сроки | Название |
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). |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".