Новый прорыв приближает умножение матриц к идеалу | Журнал Кванта

Ученые-компьютерщики — это требовательная группа. Для них недостаточно получить правильный ответ на проблему — цель почти всегда состоит в том, чтобы получить ответ как можно более эффективно.

Возьмем, к примеру, умножение матриц или массивов чисел. В 1812 году французский математик Жак Филипп Мари Бине разработал базовый набор правил, которым мы до сих пор обучаем студентов. Это работает прекрасно, но другие математики нашли способы упростить и ускорить процесс. Теперь задача ускорение процесса Умножение матриц лежит на стыке математики и информатики, где исследователи продолжают совершенствовать этот процесс и по сей день, хотя в последние десятилетия достижения были довольно скромными. С 1987 года числовые улучшения в умножении матриц были «небольшими и … чрезвычайно трудными для достижения», сказал он. Франсуа Ле Галль, ученый-компьютерщик из Университета Нагои.

Теперь трое исследователей — Ран Дуань и Жэньфэй Чжоу из Университета Цинхуа и Хунсюнь Ву из Калифорнийского университета в Беркли — сделали большой шаг вперед в решении этой извечной проблемы. Их новые результаты, представленный в ноябре прошлого года на конференции «Основы компьютерных наук», основан на неожиданной новой технологии, сказал Ле Галль. Хотя само по себе улучшение было относительно небольшим, Ле Галль назвал его «концептуально большим, чем другие предыдущие».

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

«Это крупный технический прорыв», — сказал Уильям Кушмаул, ученый-теоретик в области информатики из Гарвардского университета. «Это самое большое улучшение в матричном умножении, которое мы видели за более чем десятилетие».

Введите матрицу

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

Традиционный способ умножения двух n-На-n матриц — путем умножения чисел из каждой строки первой матрицы на числа в столбцах второй — требуется n³ отдельные умножения. Для матриц 2х2 это означает 2³ или 8 умножений.

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

Штрассен использовал ту же идею, чтобы показать, что все более крупные n-На-n матрицы также можно умножать менее чем за n³ шаги. Ключевым элементом этой стратегии является процедура, называемая декомпозицией — разбиение большой матрицы на последовательно меньшие подматрицы, которые в конечном итоге могут оказаться размером всего 2 на 2 или даже 1 на 1 (это просто отдельные числа).

По мнению ученых, объяснение разделения гигантского массива на крошечные части довольно простое. Вирджиния Василевска Уильямс, ученый-компьютерщик из Массачусетского технологического института и соавтор одной из новых статей. «Человеку трудно взглянуть на большую матрицу (скажем, порядка 100х100) и придумать наилучший возможный алгоритм», — сказала Василевска Уильямс. Даже матрицы 3х3 еще не решены полностью. «Тем не менее, можно использовать быстрый алгоритм, который уже разработан для маленьких матриц, чтобы получить быстрый алгоритм и для больших матриц».

Ключом к скорости, как определили исследователи, является сокращение количества шагов умножения, снижение показателя степени с n³ (для стандартного метода) столько, сколько смогут. Минимально возможное значение, n², по сути, столько же времени, сколько нужно, чтобы просто написать ответ. Ученые-компьютерщики называют этот показатель омегой, ω, с n^ω это наименьшее количество возможных шагов, необходимых для успешного умножения двух n-На-n матрицы как n вырастает очень большим. «Цель этой работы, — сказал Чжоу, который также является соавтором статьи, опубликованной в январе 2024 года, — состоит в том, чтобы увидеть, насколько близко к 2 вы можете подойти и можно ли этого достичь в теории».

Лазерный фокус

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

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

Вот упрощенный способ мышления о том, как эти различные элементы сочетаются друг с другом. Начнем с двух больших матриц A и B, которые вы хотите перемножить. Сначала вы разлагаете их на множество более мелких подматриц или блоков, как их иногда называют. Далее вы можете использовать алгоритм Копперсмита и Винограда в качестве своего рода инструкции по обработке и, в конечном итоге, сборке блоков. «Он говорит мне, что умножать, что добавлять и какие записи куда идти» в матрице продуктов C, — сказала Василевска Уильямс. «Это всего лишь рецепт создания C из A и B».

Однако есть одна загвоздка: иногда у вас возникают блоки, имеющие общие записи. Оставить их в продукте было бы все равно, что посчитать эти записи дважды, поэтому в какой-то момент вам нужно будет избавиться от этих дублирующихся терминов, называемых дублированием. Исследователи делают это, «убивая» блоки, в которых они находятся, — устанавливая их компоненты равными нулю, чтобы исключить их из расчета.

Именно здесь наконец вступает в действие лазерный метод Штрассена. «Лазерный метод обычно работает очень хорошо и обычно находит хороший способ уничтожить подмножество блоков, чтобы устранить перекрытие», — сказал Ле Галл. После того, как лазер устранил или «сжег» все перекрытия, вы можете построить конечную матрицу продукта C.

Объединение этих различных методов приводит к созданию алгоритма умножения двух матриц с намеренно скудным числом умножений в целом — по крайней мере, в теории. Лазерный метод не претендует на практичность; это просто способ подумать об идеальном способе умножения матриц. «Мы никогда не запускаем этот метод [на компьютере]», — сказал Чжоу. «Мы это анализируем».

И именно этот анализ привел к самому большому улучшению омеги за более чем десятилетие.

Обнаружена потеря

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

Лазерный метод заключается в маркировке перекрывающихся блоков как мусора, предназначенного для утилизации; остальные блоки считаются достойными и будут сохранены. Однако процесс отбора несколько рандомизирован. Блок, оцененный как мусор, на самом деле может оказаться полезным. Это не было полной неожиданностью, но, изучив многие из этих случайных вариантов, команда Дуана определила, что лазерный метод систематически недооценивает блоки: нужно сохранять больше блоков и меньше выбрасывать. И, как это обычно бывает, меньше отходов приводит к большей эффективности.

«Возможность хранить больше блоков без перекрытия приводит к… более быстрому алгоритму умножения матриц», — сказал Ле Галл.

Доказав существование этой потери, команда Дуана изменила способ маркировки блоков лазерным методом, существенно сократив количество отходов. В результате они установили новую верхнюю границу для омеги на отметке 2.371866 — улучшение по сравнению с предыдущей верхней границей 2.3728596. установить в 2020 Джош Алман и Василевска Уильямс. Это может показаться скромным изменением: граница снижается примерно на 0.001. Но это самое большое улучшение, которое ученые наблюдали с 2010 года. Для сравнения, результат Василевской Уильямс и Алмана за 2020 год улучшился по сравнению с его предшественником всего на 0.00001.

Но больше всего исследователей волнует не только сам новый рекорд, который просуществовал недолго. Это также тот факт, что статья открыла новый путь к улучшению, который до этого оставался совершенно незамеченным. По словам Ле Галля, на протяжении почти четырех десятилетий все полагались на один и тот же лазерный метод. «А потом они обнаружили, что мы можем добиться большего».

В документе, опубликованном в январе 2024 года, этот новый подход был усовершенствован, что позволило Василевской Уильямс, Чжоу и их соавторам еще больше сократить скрытые потери. Это привело к дополнительному улучшению верхней границы омеги, снизив ее до 2.371552. Авторы также обобщили тот же метод, чтобы улучшить процесс умножения прямоугольных (n-На-m) матрицы — процедура, имеющая приложения в теории графов, машинном обучении и других областях.

Некоторый дальнейший прогресс в этом направлении почти неизбежен, но есть пределы. В 2015 году Ле Галль и двое его соавторов доказанный что нынешний подход — лазерный метод в сочетании с рецептом Копперсмита-Винограда — не может дать омегу ниже 2.3078. Чтобы внести какие-либо дальнейшие улучшения, сказал Ле Галль, «вам необходимо улучшить первоначальный [подход] Копперсмита и Винограда, который практически не изменился с 1987 года.". Но пока лучшего способа никто не придумал. Возможно, его даже не будет.

«Улучшение омега-кислот на самом деле является частью понимания этой проблемы», — сказал Чжоу. «Если мы сможем хорошо понять проблему, мы сможем разработать для нее лучшие алгоритмы. [И] люди все еще находятся на самых ранних стадиях понимания этой извечной проблемы».