13 июня в 16:00 состоится заседание объединённого междисциплинарного научного семинара «Проблемы информатики и управления» под руководством научного руководителя ФИЦ ИУ РАН академика РАН Соколова Игоря Анатольевича.
На семинаре будет представлен доклад на тему: «Быстрое умножение матриц, комплекснозначные решения уравнений Брента и нелинейные задачи наименьших квадратов».
Докладчик: главный научный сотрудник ФИЦ ИУ РАН д.ф.-м.н. Капорин Игорь Евгеньевич.
Аннотация доклада
Матричное умножение является фундаментальной операцией вычислительной линейной алгебры. В его терминах можно выразить, например, вычисление треугольных разложений матриц, обращение матриц, решение задач линейного программирования, решение задач на графах, отыскание совпадений в строках, обучение глубоких нейросетей и другие задачи анализа больших данных. Разработка быстрых алгоритмов умножения матриц большого размера идет с 1968 года (результат Штрассена). В этой области получено много интересных результатов, среди которых есть практически значимые. С другой стороны, даже для матриц малого размера остается немало неясностей и нерешенных проблем.
Отыскание нетривиальных трилинейных канонических разложений тензора матричного произведения (известных также как уравнения Брента) соответствует построению асимптотически быстрых алгоритмов для перемножения матриц. Таким образом, исследование и численное решение уравнений Брента является важной задачей, хотя и весьма сложной с вычислительной точки зрения при сколько-нибудь значительных размерах матриц.
Предлагаются способы параметризации уравнений Брента, основанные на использовании свойств симметрии и инвариантности тензора матричного произведения, которые позволяют многократно уменьшить как число уравнений, так и число неизвестных.
Численное решение получаемых трилинейных или кубических систем уравнений осуществляется посредством сведения к нелинейной задаче наименьших квадратов и применения к ней специально разработанного итерационного метода, не требующего вычисления производных. Найденные решения параметризованных уравнений Брента, в большинстве случаев имеют ранг не больший (а иногда и меньший) по сравнению с известными результатами, полученными в течение последних нескольких десятилетий.
Так, получены более быстрые по сравнению с известными алгоритмы перемножения двух 4х4-матриц за 48 умножений и 2х4-матрицы на 4х5-матрицу за 32 умножения.
Семинар проходит в конференц-зале ФИЦ ИУ РАН по адресу: ул. Вавилова д. 44, корп. 2, пом. 124 в гибридном формате с возможностью дистанционного участия. По вопросам очного посещения семинара лицами, не работающими в ФИЦ ИУ РАН, удаленного подключения к заседанию, и иным вопросам, связанным с работой семинара, просьба обращаться по эл. почте: seminar@frccsc.ru
