Новый способ существенно уменьшает время вычисления перемножения матриц
Трое учёных — Ран Дуань и Жэньфэй Чжоу из Университета Цинхуа и Хунсюнь Ву из Калифорнийского университета в Беркли — сделали большой шаг вперед в решении математической проблемы. Их результаты, представленные в ноябре прошлого года на конференции Foundations of Computer Science, основаны на неожиданной новой методике, которая позволяет существенно ускорить процесс умножения матриц. Традиционный способ умножения двух матриц размером n на n — путем умножения чисел из каждой строки первой матрицы на числа в столбцах второй — требует n в кубе отдельных умножений. Для матриц 2 на 2 это 8 умножений. В работе показано на сколько близко можно приблизится от куба ко второй степени.
Жэньфэй Чжоу.
Немного истории
В 1812 году французский математик Жак Филипп Мари Бине разработал базовый набор правил перемножения матриц и массивов чисел, которым мы до сих пор обучают студентов. С развитием компьютерных технологий стал вопрос об ускорении процесса перемножения.
Это может показаться неясной проблемой, но умножение матриц — фундаментальная вычислительная операция. Он включен в большую часть алгоритмов, которые люди используют каждый день для самых разных задач: от отображения более четкой компьютерной графики до решения логистических задач в теории сетей. И, как и в других областях вычислений, скорость имеет первостепенное значение. Даже небольшие улучшения могут в конечном итоге привести к значительной экономии времени, вычислительной мощности и денег. Но на данный момент теоретики в основном заинтересованы в том, чтобы выяснить, насколько быстрым может быть этот процесс.
Традиционный способ умножения двух матриц размером n на n — путем умножения чисел из каждой строки первой матрицы на числа в столбцах второй — требует n3 отдельных умножений. Для матриц 2 на 2 это означает 23 или 8 умножений.
В 1969 году математик Фолькер Штрассен открыл более сложную процедуру, позволяющую умножать матрицы 2 на 2 всего за семь мультипликативных шагов и 18 сложений. Два года спустя ученый-компьютерщик Шмуэль Виноград продемонстрировал, что семь действительно является абсолютным минимумом для матриц 2х2.
Штрассен использовал ту же идею, чтобы показать, что все большие матрицы размером n на n также можно умножить менее чем за n3 шагов. Ключевым элементом этой стратегии является процедура, называемая декомпозицией — разбиение большой матрицы на последовательно меньшие подматрицы, которые в конечном итоге могут оказаться размером всего 2 на 2 или даже 1 на 1 (это просто отдельные числа).
Ключом к скорости, как определили исследователи, является сокращение количества шагов умножения, максимально уменьшив показатель степени с n3 (для стандартного метода). Наименьшее возможное значение, n2, по сути, равно времени, необходимому только для написания ответа. Ученые-компьютерщики называют этот показатель омегой, ω, где nω — это наименьшее количество возможных шагов, необходимых для успешного умножения двух матриц размером n на n, когда n становится очень большим.
Лазерный фокус
В 1986 году Штрассен совершил еще один большой прорыв, когда представил так называемый лазерный метод умножения матриц. Штрассен использовал его, чтобы установить максимальное значение омега-кислоты 2,48. Этот метод постоянно продолжают совершенствовать. Год спустя Виноград и Дон Копперсмит представили новый алгоритм, который прекрасно дополнил лазерный метод.
Скрытая потеря
Статья, опубликованная прошлым летом Дуанем, Чжоу и Ву, показала, что процесс Штрассена все еще можно значительно ускорить. Все это произошло из-за концепции, которую они назвали скрытой потерей, скрытой глубоко в предыдущих анализах — «результате непреднамеренного уничтожения слишком большого количества блоков», — сказал Чжоу.
Лазерный метод заключается в маркировке перекрывающихся блоков как мусора, предназначенного для утилизации; остальные блоки считаются достойными и будут сохранены. Однако процесс отбора несколько рандомизирован. Блок, оцененный как мусор, на самом деле может оказаться полезным. Это не было полной неожиданностью, но, изучив многие из этих случайных вариантов, команда Дуана определила, что лазерный метод систематически недооценивает блоки: нужно сохранять больше блоков и меньше выбрасывать. И, как это обычно бывает, меньше отходов приводит к большей эффективности.
Доказав существование этой потери, команда Дуана изменила способ маркировки блоков лазерным методом, существенно сократив количество отходов. В результате они установили новую верхнюю границу омеги на отметке 2,371866 — улучшение по сравнению с предыдущей верхней границей 2,3728596, установленной в 2020 году Джошем Алманом и Василевской Уильямс. Это может показаться скромным изменением: граница снижается примерно на 0,001. Но это самое большое улучшение, которое ученые наблюдали с 2010 года. Для сравнения, результат Василевской Уильямс и Алмана за 2020 год улучшился по сравнению с его предшественником всего на 0,00001.
В документе, опубликованном в январе 2024 года, этот новый подход был усовершенствован, что позволило Василевской Уильямс, Чжоу и их соавторам еще больше сократить скрытые потери. Это привело к дополнительному улучшению верхней границы омеги, снизив ее до 2,371552. Авторы также обобщили эту же технику для улучшения процесса умножения прямоугольных (n на m) матриц — процедуры, которая находит применение в теории графов, машинном обучении и других областях.
