Развитие алгоритмов матричного умножения

№126-1,

Физико-математические науки

Проведен анализ скорости алгоритмов матричного умножения. Сформулированы перспективы развития тензорного подхода к умножению матриц.

Похожие материалы

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

Сложность классического алгоритма матричного умножения n3. Другими словами, чтобы умножить матрицы размером 2×2 необходимо провести восемь умножений.

Теоретически предельная скорость матричного умножения это n2, то есть умножение двух матриц размером n×n теоретически невозможно быстрее, чем за n2 шагов. Если бы вторая степень была достижима, то матричное умножение можно выполнять максимально быстро, насколько это физически возможно. Матрицы представляют собой массивы чисел. Когда две матрицы согласованы (число столбцов в первом сомножителе равно числу строк во втором), их можно перемножить, чтобы получить третью. Например, две матрицы 2 × 2, их произведение также будет матрицей 2 × 2, содержащей четыре элемента. В более общем смысле, произведение пары матриц размером n х n представляет собой другую матрицу размером n × n с n2 элементами. Поэтому наименьшее возможное количество шагов для умножения пар матриц это n2, то есть количество шагов, необходимое просто для записи ответа. Отсюда и название «вторая степень».

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

Путем многократного разбиения больших матриц на более мелкие и с помощью алгоритма Штрассена можно сокращать количество шагов на каждом этапе. В целом этот алгоритм увеличил скорость умножения матриц с n3 до n2.81 мультипликативных шагов, что даёт выигрыш на больших плотных матрицах начиная, примерно, от 64×64.

Проблема быстрого умножения матриц, поставленная Штрассеном по сей день не решена ни в теоретическом, ни в практическом плане.

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

Умножение матриц и задача, связанная с тензорами, эквивалентны друг другу, но для решения последней имеются более быстрые процедуры.

В 1981 году Арнольд Шёнхаге использовал этот подход, чтобы доказать, что умножение матриц возможно выполнить за n2.522 шагов. Позднее Штрассен назвал этот подход «лазерным методом» (laser method). Лазерный метод считает для значений N с меньшими ошибками округления, чем при использовании метода Штрассена с использованием какого-либо дифференциального уравнения или численного метода.

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

В 1990 году самый быстрый из известных алгоритмов умножения матриц, созданный Копперсмитом и Виноградом, выполнялся за время n2,3755.

В 2012 году Вирджиния Василевска Уильямс из Массачусетского технологического института рамках лазерного метода получила n2.372873.

В 2014 году Франсуа Ле Галлю достиг скорости n2.3728639. Этот результат получен путем анализа более высоких тензорных мощностей определенного тождества Копперсмита и Винограда.

В октябре 2020 года Вирджиния Василевска Уильямс и Джош Алман из Гарвардского университета опубликовали статью «A Refined Laser Method and Faster Matrix Multiplication», где они описали самый быстрый на настоящий момент способ перемножения двух матриц за n2.3728596 шагов. Однако этот алгоритм галактического масштаба, то есть только для данных галактического размера, поскольку содержит огромные константы и не может быть реализован на практике.

Основные этапы решения задачи быстрого матричного умножения приведены в таблице 1.

Таблица 1. Теоретические исследования производительности матричного умножения

Когда

Автор

Скорость

Примечание

n3

Скорость матричного умножения при тривиальном подходе

1969

Фолькер Штрассен

n2.81

Для матриц 2*2 предложен набор соотношений, которые позволили заменить одно из восьми умножений 14 дополнительными сложениями.

1981

Арнольд Шёнхаге

n2.522

Применение тензоров при матричном умножении (laser method)

1990

Копперсмит и Виноград

n2,3755

Усовершенствованный laser method

2012

Вирджиния Василевска Уильямс

n2.372873

Усовершенствованный laser method

2014

Франсуа Ле Галлю

n2.3728639

Усовершенствованный laser method

n2

Теоретический предел скорости матричного умножения

Таким образом, можно констатировать, что на настоящий момент резервы тензорного способа матричного умножения исчерпаны. Применение данного подхода позволило пройти почти 2/3 пути от тривиального до идеального решения задачи матричного умножения.

Список литературы

  1. Matrix Multiplication Inches Closer to Mythic Goal [Электронный ресурс] URL: https://science-education.ru/ru/article/view?id=25956 (дата обращения: 31.05.2021).
  2. Alman, Josh & Williams, Virginia. (2021). A Refined Laser Method and Faster Matrix Multiplication. 10.1137/1.9781611976465.32.