[Перевод] Матричное умножение. Медленное достижение мифической цели
В недавней работе был установлен новый рекорд скорости по умножению двух матриц. Она также знаменует и конец эпохи для метода, который ученые применяли для исследований на протяжении десятилетий.
Математики стремятся к достижению мифической цели — второй степени (exponent two), то есть к умножению пары матриц n х n всего за n2 шагов. Исследователи подбираются все ближе к своей цели, но получится ли у них когда-нибудь достичь ее?
Для специалистов в области Computer Science и математиков сама идея о «второй степени» связана с представлениями о совершенном мире.
«Трудно разграничить научное мышление и беспочвенные мечтания», — признается Крис Уманс из Калифорнийского технологического института. «Я хочу, чтобы степень была равна двум, потому что это красиво».
С точки зрения необходимого количества шагов «вторая степень» — это идеальная скорость выполнения одной из самых фундаментальных математических операций — матричного умножения. Если вторая степень достижима, то матричное умножение получится выполнять максимально быстро, насколько это физически возможно. Если это не так, то мы застряли в мире, который не соответствует нашим мечтам.
Матрицы представляют собой массивы чисел. Когда две матрицы согласованы (число столбцов в первом сомножителе равно числу строк во втором), их можно перемножить, чтобы получить третью. Например, если вы начнете с пары матриц 2×2, их произведение также будет матрицей 2×2, содержащей четыре элемента. В более общем смысле, произведение пары матриц размером n х n представляет собой другую матрицу размером n х n с n2 элементами.
Поэтому наименьшее возможное количество шагов для умножения пар матриц это n2, то есть количество шагов, необходимое просто для записи ответа. Отсюда и название «вторая степень».
И хотя никто точно не знает, можно ли этого достичь, исследователи продолжают продвигаться в этом направлении.
Статья, опубликованная в октябре, подбирается к цели еще ближе и описывает самый быстрый на данный момент метод умножения двух матриц. Результат, который получили Джош Алман, докторант Гарвардского университета, и Вирджиния Василевска Уильямс из Массачусетского технологического института, уменьшает степень предыдущего лучшего показателя примерно на одну стотысячную. Это действительно большое достижение в данной области, добытое кропотливым трудом.
Чтобы получше разобраться в этом процессе и понять, как его можно усовершенствовать, давайте начнем с пары матриц 2×2, A и B. При вычислении каждого элемента их произведения вы используете соответствующую строку из A и соответствующий столбец из B. Чтобы получить верхний правый элемент, умножьте первое число в первой строке A на первое число во втором столбце B, затем умножьте второе число в первой строке A на второе число во втором столбце B и сложите эти два произведения.
Самуэль Веласко / Quanta Magazine
Эта операция известна как получение «скалярного произведения» строки со столбцом (иногда называется «внутренним произведением»). Чтобы вычислить другие элементы в произведении матриц, повторите процедуру с соответствующими строками и столбцами.
В целом, классический метод умножения матриц 2×2 состоит из восьми умножений и нескольких сложений. Как правило, этот способ умножения двух матриц размера n х n требует n3 умножений.
С увеличением размера матриц количество умножений, необходимых для нахождения их произведения, растет намного быстрее, чем количество сложений. Чтобы найти произведение матриц 2×2 требуется всего восемь промежуточных умножений, а чтобы найти произведение матриц 4×4 их требуется уже 64. Однако количество сложений, необходимых для получения суммы этих матриц, не так значительно отличается. Обычно количество сложений равно количеству элементов в матрице, то есть четыре для матриц 2×2 и 16 для матриц 4×4. Эта разница между сложением и умножением позволяет понять, почему исследователи измеряют скорость умножения матриц исключительно с точки зрения количества требуемых умножений.
«Умножения — это наше всё, — утверждает Уманс, — Показатель степени в итоге полностью зависит только от количества умножений. Сложения в некотором смысле исчезают».
На протяжении веков люди считали, что n3 — это самый быстрый способ умножения матриц. По имеющимся сведениям, в 1969 году Фолькер Штрассен намеревался доказать, что невозможно умножить матрицы 2×2, используя менее восьми умножений. Видимо, он все-таки не смог найти доказательства, а через некоторое время и понял почему: на самом деле, существует способ сделать это с помощью семи умножений!
Штрассен придумал сложный набор соотношений, которые позволили заменить одно из этих восьми умножений 14 дополнительными сложениями. Может показаться, что разница совершенно незначительна, но она оправдывает себя, так как умножение вносит больший вклад, чем сложение. Найдя способ избавиться от одного умножения для маленьких матриц 2×2, Штрассен открыл возможность, которую он мог использовать при умножении бOльших матриц.
«Это крошечное изменение приводит к огромным улучшениям в работе с большими матрицами», — говорит Уильямс.
Вирджиния Василевска Уильямс из Массачусетского технологического института и Джош Алман из Гарвардского университета открыли самый быстрый способ перемножения двух матриц за n2.3728596 шагов. Джаред Чарни; Ричард Т.К. Хоук
Предположим, вы хотите перемножить пару матриц 8×8. Один из способов сделать это — разбить каждую большую матрицу на четыре матрицы размером 4×4 так, чтобы каждая имела по четыре элемента. Поскольку элементы матрицы также могут являться матрицами, вы можете считать исходные матрицы парой матриц 2×2, каждый из четырех элементов которых сам по себе является матрицей 4×4. Посредством некоторых манипуляций каждая из этих матриц размером 4×4 может быть разбита на четыре матрицы размером 2×2.
Смысл этого многократного разбиения больших матриц на более мелкие заключается в том, что можно снова и снова применять алгоритм Штрассена к меньшим матрицам и с помощью его метода сокращать количество шагов на каждом этапе. В целом алгоритм Штрассена увеличил скорость умножения матриц с n3 до n2.81 мультипликативных шагов.
Следующий важный шаг в развитии идеи произошел в конце 1970-х, когда появился принципиально новый подход к решению этой задачи. Он подразумевает перевод матричного умножения в другую вычислительную задачу линейной алгебры с использованием объектов, называемых тензорами. Тензоры, используемые в этой задаче, представляют собой трехмерные массивы чисел, состоящие из множества различных частей, каждая из которых выглядит как небольшая задача на умножение матриц.
Умножение матриц и эта задача, связанная с тензорами, в определенном смысле эквивалентны друг другу, но для решения последней исследователи уже имели более быстрые процедуры. Таким образом, перед ними встала задача определить «обменный курс» между ними: Матрицы какого размера можно перемножить при тех же вычислительных затратах, которые требуются для решения тензорной задачи?
«Это очень распространенная в теоретической информатике концепция: преобразовывать задачи и проводить аналогию между ними, чтобы показать, что они одинаково простые или сложные», — сказал Алман.
В 1981 году Арнольд Шёнхаге использовал этот подход, чтобы доказать, что умножение матриц возможно выполнить за n2.522 шагов. Позднее Штрассен назвал этот подход «лазерным методом» (laser method).
За последние несколько десятилетий каждое улучшение в процессе умножения матриц происходило за счет усовершенствования лазерного метода, поскольку исследователи находили все более эффективные способы трансформации задачи. В своем новом доказательстве Алман и Уильямс стирают различие между 2 задачами и показывают, что уменьшить число умножений возможно. «В целом Джош и Вирджиния нашли способ применить машинные вычисления в рамках лазерного метода и получили лучшие на настоящий момент результаты», — сказал Генри Кон из Microsoft Research.
В их статье теоретическое ограничение скорости умножения матриц улучшено до n2.3728596.
Также благодаря этому исследованию Уильямс может вернуть себе корону в области матричного умножения, которую она по праву получила в 2012 году (n2.372873), а затем уступила в 2014 году Франсуа Ле Галлю (n2.3728639).
Но, несмотря на все эти гонки и победы, становится ясно, что в случае с этим подходом действует закон убывающей доходности, или убывающей отдачи. Скорее всего, усовершенствование Алмана и Уильямс почти полностью исчерпало возможности лазерного метода, но так и не позволило достичь конечной теоретической цели.
«Маловероятно, что получится приблизиться ко второй степени, используя это семейство методов», — отметил Уманс.
Для этого потребуется открытие новых методов и стойкая вера в то, что это вообще возможно.
Уильямс вспоминает один из разговоров со Штрассеном об этом: «Я спросила его, считает ли он, что возможно получить вторую степень для матричного умножения, и он ответил: «Нет, нет, нет, никогда!».
