Алгоритм умножения матриц

Алгоритм умножения матриц

Поскольку умножение матриц является центральной операцией во многих числовых алгоритмах , много работы было вложено в повышение эффективности алгоритмов умножения матриц . Применение умножения матриц в вычислительных задачах можно найти во многих областях, включая научные вычисления и распознавание образов , а также в, казалось бы, несвязанных задачах, таких как подсчет путей в графе . ^[1] Для умножения матриц было разработано множество различных алгоритмов на различных типах оборудования, включая параллельные и распределенные системы, где вычислительная работа распределена по нескольким процессорам (возможно, по сети).

Непосредственное применение математического определения умножения матриц дает алгоритм, который ^{требует} времени порядка n3 полевых операций для умножения двух матриц ^{размера} n × n по этому полю ( Θ( n3 ) в обозначении большого O ). Лучшие асимптотические границы времени, необходимого для умножения матриц, были известны со времен алгоритма Штрассена в 1960-х годах, но оптимальное время (то есть вычислительная сложность умножения матриц ) остается неизвестным. По состоянию на апрель 2024 года ^{[обновлять]}лучшая объявленная оценка асимптотической сложности алгоритма матричного умножения составляет время O ( n ^2,371552 ) , данное Уильямсом , Сюй, Сюй и Чжоу. ^{[2] [3]} Это улучшает оценку времени O( n ^2,3728596 ) , данную Алманом и Уильямсом. ^{[4] [5]} Однако этот алгоритм является галактическим из-за больших констант и не может быть реализован на практике.

Итерационный алгоритм

Определение умножения матриц таково: если C = AB для матрицы A размера n × m и матрицы B размера m × p , то C является матрицей размера n × p с элементами

${\displaystyle c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}.}$

Исходя из этого, можно построить простой алгоритм, который циклически перебирает индексы i от 1 до n и j от 1 до p , вычисляя вышеуказанное с помощью вложенного цикла:

• Входные данные: матрицы A и B.
• Пусть C — новая матрица соответствующего размера.
• Для i от 1 до n :
  • Для j от 1 до p :
    • Пусть сумма = 0
    • Для k от 1 до m :
      • Установить сумму ← sum + A _ik × B _kj
    • Установить C _ij ← сумма
• Возврат С

Этот алгоритм требует времени Θ( nmp ) (в асимптотических обозначениях ). ^[1] Обычное упрощение для целей анализа алгоритма состоит в том, чтобы предположить, что все входные данные представляют собой квадратные матрицы размера n × n , и в этом случае время выполнения равно Θ( n ³ ) , то есть кубическое по размеру размерности. . ^[6]

Поведение кэша

Иллюстрация порядка строк и столбцов

Три цикла итеративного умножения матриц можно произвольно менять местами без влияния на корректность или асимптотическое время выполнения. Однако порядок может оказать значительное влияние на практическую производительность из-за шаблонов доступа к памяти и использования кэша алгоритма; ^[1] какой порядок лучше, также зависит от того, хранятся ли матрицы в порядке по строкам, по столбцам или в их сочетании.

В частности, в идеализированном случае полностью ассоциативного кэша, состоящего из M байтов и b байтов на строку кэша (т.е. ⁠М/б⁠ строк кэша), приведенный выше алгоритм неоптимален для A и B , хранящихся в порядке строк. Когда n > ⁠М/б⁠ каждая итерация внутреннего цикла (одновременный просмотр строки A и столбца B ) вызывает промах в кэше при доступе кэлементу B. Это означает, что в худшем случаеалгоритм допускает Θ( n ³ ) промахов в кэше. По состоянию на 2010 год^{[обновлять]}скорость памяти по сравнению со скоростью процессоров такова, что промахи в кэше, а не фактические вычисления, доминируют во времени работы для матриц значительного размера. ^[7]

Оптимальным вариантом итерационного алгоритма для A и B в разбивке по строкам является мозаичная версия, в которой матрица неявно делится на квадратные плитки размером √ M на √ M : ^{[7] [8]}

• Входные данные: матрицы A и B.
• Пусть C — новая матрица соответствующего размера.
• Выберите размер плитки T = Θ( √ M )
• Для I от 1 до n с шагом T :
  • Для J от 1 до p с шагом T :
    • Для K от 1 до m с шагом T :
      • Умножим A _{I : I + T , K : K + T} и B _{K : K + T , J : J + T} на C _{I : I + T , J : J + T} , то есть:
      • Для i от I до min( I + T , n ) :
        • Для j от J до min( J + T , p ) :
          • Пусть сумма = 0
          • Для k от K до min( K + T , m ) :
            • Установить сумму ← sum + A _ik × B _kj
          • Установить C _ij ← C _ij + сумма
• Возврат С

В идеализированной модели кэша этот алгоритм требует только Θ( ⁠№ ³/б √ М⁠ ) ​​промахи в кэше; делитель b √ M на современных машинах составляет несколько порядков, так что фактические вычисления доминируют во времени выполнения, а не промахи в кэше. ^[7]

Алгоритм «разделяй и властвуй»

Альтернативой итеративному алгоритму является алгоритм умножения матриц « разделяй и властвуй» . Это зависит от разделения блоков

${\displaystyle C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},}$

который работает для всех квадратных матриц, размеры которых являются степенями двойки, т. е. формы имеют размер 2 ⁿ × 2 ⁿ для некоторого n . Матричный продукт теперь

${\displaystyle {\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}}$

который состоит из восьми умножений пар подматриц с последующим шагом сложения. Алгоритм «разделяй и властвуй» рекурсивно вычисляет меньшие умножения , используя скалярное умножение c ₁₁ = a ₁₁ b ₁₁ в качестве базового случая.

Сложность этого алгоритма как функция от n определяется рекуррентностью ^[6]

${\displaystyle T(1)=\Theta (1);}$

${\displaystyle T(n)=8T(n/2)+\Theta (n^{2}),}$

с учетом восьми рекурсивных вызовов матриц размера n /2 и Θ( n2 ) ^для поэлементного суммирования четырех пар результирующих матриц. Применение основной теоремы для повторений по принципу «разделяй и властвуй» показывает, что эта рекурсия имеет решение Θ( n ³ ) , такое же, как и итерационный алгоритм. ^[6]

Неквадратные матрицы

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

• Входные данные: матрицы A размера n × m , B размера m × p .
• Базовый случай: если max( n , m , p ) ниже некоторого порога, используйте развернутую версию итерационного алгоритма.
• Рекурсивные случаи:

• Если max( n , m , p ) = n , разделите A горизонтально:

${\displaystyle C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}}$

• В противном случае, если max( n , m , p ) = p , разделите B вертикально:

${\displaystyle C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}}$

• В противном случае max( n , m , p ) = m . Разделите A вертикально и B горизонтально:

${\displaystyle C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}}$

Поведение кэша

Частота промахов в кэше при рекурсивном умножении матриц такая же, как и в мозаичной итеративной версии, но, в отличие от этого алгоритма, рекурсивный алгоритм не учитывает кэш : ^[9] для получения оптимальной производительности кэша не требуется параметр настройки, и он ведет себя хорошо в мультипрограммной среде, где размеры кэша фактически динамичны из-за того, что другие процессы занимают пространство кэша. ^[7] (Простой итерационный алгоритм также не учитывает кэш, но на практике он работает намного медленнее, если расположение матрицы не адаптировано к алгоритму.)

Количество промахов кэша, возникающих в результате этого алгоритма, на машине с M строками идеального кэша, каждая размером b байт, ограничено ^{[9] : 13.}

${\displaystyle \Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)}$

Субкубические алгоритмы

Улучшение оценок показателя ω с течением времени для вычислительной сложности умножения матриц . ${\displaystyle O(n^{\omega })}$

Существуют алгоритмы, которые обеспечивают лучшее время работы, чем простые алгоритмы. Первым был открыт алгоритм Штрассена , разработанный Фолькером Штрассеном в 1969 году и часто называемый «быстрым умножением матриц». Он основан на способе умножения двух матриц размера 2 × 2 , который требует всего 7 умножений (вместо обычных 8) за счет нескольких дополнительных операций сложения и вычитания. Рекурсивное применение этого метода дает алгоритм с мультипликативной стоимостью . Алгоритм Штрассена более сложен, и численная стабильность снижается по сравнению с наивным алгоритмом ^[10] , но он быстрее в случаях, когда n > 100 или около того ^[1] и появляется в нескольких библиотеках, таких как BLAS . ^[11] Это очень полезно для больших матриц в точных областях, таких как конечные поля , где численная стабильность не является проблемой. ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$

Поскольку алгоритм Штрассена фактически используется в практическом численном программном обеспечении и системах компьютерной алгебры, улучшение констант, скрытых в большой нотации O, имеет свои преимущества. Ниже приведена таблица, в которой сравниваются ключевые аспекты улучшенной версии, основанной на рекурсивном умножении блочных матриц 2x2 посредством умножения 7-блочных матриц. Как обычно дает размеры матрицы и обозначает объем памяти. ${\displaystyle n}$ ${\displaystyle M}$

Известно, что алгоритм Штрассена с шагом блочной матрицы 2x2 требует не менее 7 умножений блочной матрицы. В 1976 году Проберт ^[15] показал, что такой алгоритм требует не менее 15 сложений (включая вычитания), однако скрытым предположением было то, что блоки и блочная матрица 2x2 представлены в одном и том же базисе. Карштадт и Шварц произвели вычисления в разных базисах и обменяли 3 сложения на менее затратные преобразования базисов. Они также доказали, что при использовании разных базисов нельзя опускаться ниже 12 сложений за шаг. В последующей работе Бениамини и др. ^[16] применили этот трюк с изменением базы к более общим разложениям, чем блочные матрицы 2x2, и улучшили ведущую константу для их времени выполнения.

В теоретической информатике остается открытым вопрос, насколько хорошо алгоритм Штрассена можно улучшить с точки зрения асимптотической сложности . Показатель умножения матрицы , обычно обозначаемый , представляет собой наименьшее действительное число, для которого любая матрица над полем может быть перемножена с помощью операций с полем. На данный момент лучшими являются Уильямс , Сюй , Сюй и Чжоу. ^{[2] [4]} Этот алгоритм, как и все другие недавние алгоритмы в этом направлении исследований, является обобщением алгоритма Копперсмита-Винограда, который был предложен Доном Копперсмитом и Шмуэлем Виноградом в 1990 году. ^[17] Концептуальная идея этих алгоритмов. Алгоритмы аналогичны алгоритму Штрассена: разработан способ умножения двух k × k -матриц с числом умножений менее k ³ , и этот метод применяется рекурсивно. Однако постоянный коэффициент, скрытый обозначением Big O, настолько велик, что эти алгоритмы имеют смысл только для матриц, которые слишком велики для обработки на современных компьютерах. ^{[18] [19]} ${\displaystyle \omega }$ ${\displaystyle n\times n}$ ${\displaystyle n^{\omega +o(1)}}$ ${\displaystyle \omega }$ ${\displaystyle \omega <2.371552}$

Алгоритм Фрейвалдса — это простой алгоритм Монте - Карло , который по матрицам A , B и C проверяет за время Θ( n2 ) ^, если AB = C.

АльфаТензор

В 2022 году DeepMind представила AlphaTensor — нейронную сеть , которая использовала аналогию с однопользовательской игрой для изобретения тысяч алгоритмов умножения матриц, включая некоторые из них, ранее обнаруженные людьми, а некоторые — нет. ^[20] Операции были ограничены некоммутативным основным полем (нормальная арифметика) и конечным полем ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ (арифметика по модулю 2). Лучший найденный «практический» алгоритм (явное разложение тензора матричного умножения низкого ранга) работал за O(n ^2,778 ). ^[21] Нахождение разложений низкого ранга таких тензоров (и не только) NP-трудно; оптимальное умножение даже для матриц 3х3 остается неизвестным даже в коммутативном поле. ^[21] Для матриц 4x4 компания AlphaTensor неожиданно обнаружила решение с 47 шагами умножения, что является улучшением по сравнению с 49 шагами, необходимыми для алгоритма Штрассена 1969 года, хотя и ограниченным арифметикой по модулю 2. Аналогично, AlphaTensor решал матрицы 5x5 за 96 шагов вместо 98 шагов Штрассена. Основываясь на неожиданном открытии существования таких улучшений, другие исследователи быстро смогли найти аналогичный независимый алгоритм 4x4 и отдельно доработали 96-шаговый алгоритм Deepmind 5x5 до 95 шагов в арифметике по модулю 2 и до 97 ^[22] в обычной арифметике. ^[23] Некоторые алгоритмы никогда раньше не были обнаружены, например, (4, 5, 5) был улучшен до 76 с 80 в обычной арифметике и арифметике по модулю 2.

Параллельные и распределенные алгоритмы

Параллелизм с общей памятью

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

${\displaystyle {\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}}$

могут выполняться независимо друг от друга, как и четыре суммирования (хотя алгоритму необходимо «объединить» умножения перед выполнением суммирования). Используя полный параллелизм задачи, можно получить алгоритм, который можно выразить в псевдокоде в стиле разветвления-объединения : ^[24]

Процедура умножения( C , A , B ) :

• Базовый случай: если n = 1 , установите c ₁₁ ← a ₁₁ × b ₁₁ (или умножьте небольшую блочную матрицу).
• В противном случае выделите место для новой матрицы T формы n × n , тогда:
  • Разделите A на A ₁₁ , A ₁₂ , A ₂₁ , A ₂₂ .
  • Разделите B на B11 , B12 , B21 , B22 ._​​​​
  • Разделить C на C11 , C12 , C21 , C22 ._​​​​
  • Разделить Т на Т ₁₁ , Т ₁₂ , Т ₂₁ , Т ₂₂ .
  • Параллельное выполнение:
    • Вилка умножения( C ₁₁ , A ₁₁ , B ₁₁ ) .
    • Вилочное умножение( C ₁₂ , A ₁₁ , B ₁₂ ) .
    • Вилка умножения( C ₂₁ , A ₂₁ , B ₁₁ ) .
    • Вилочное умножение( C ₂₂ , A ₂₁ , B ₁₂ ) .
    • Вилка умножается( T ₁₁ , A ₁₂ , B ₂₁ ) .
    • Вилка умножения( T ₁₂ , A ₁₂ , B ₂₂ ) .
    • Вилка умножения( T ₂₁ , A ₂₂ , B ₂₁ ) .
    • Вилка умножается( T ₂₂ , A ₂₂ , B ₂₂ ) .
  • Присоединяйтесь (дождитесь завершения параллельных разветвлений).
  • добавить( С , Т ) .
  • Освободить Т.​

Процедура add( C , T ) добавляет T в C поэлементно:

• Базовый случай: если n = 1 , установите c ₁₁ ← c ₁₁ + t ₁₁ (или сделайте короткий цикл, возможно, развернутый).
• В противном случае:
  • Разделить C на C11 , C12 , C21 , C22 ._​​​​
  • Разделить Т на Т ₁₁ , Т ₁₂ , Т ₂₁ , Т ₂₂ .
  • В параллели:
    • Вилка добавить( C ₁₁ , T ₁₁ ) .
    • Вилка добавить( C ₁₂ , T ₁₂ ) .
    • Вилка добавить( C ₂₁ , T ₂₁ ) .
    • Вилка добавить( C ₂₂ , T ₂₂ ) .
  • Присоединиться .

Здесь fork — это ключевое слово, которое сигнализирует, что вычисление может выполняться параллельно с остальной частью вызова функции, в то время как соединение ожидает завершения всех ранее «разветвленных» вычислений. Раздел достигает своей цели только за счет манипулирования указателями.

Длина критического пути этого алгоритма составляет Θ (log ² n ) шагов, а это означает, что на идеальной машине с бесконечным числом процессоров он занимает столько же времени; следовательно, он имеет максимально возможное ускорение Θ ( n ³ /log ² n ) на любом реальном компьютере. Алгоритм непрактичен из-за затрат на связь, связанных с перемещением данных во временную матрицу T и обратно , но более практичный вариант обеспечивает ускорение Θ( n ² ) без использования временной матрицы. ^[24]

Блочное умножение матриц. В 2D-алгоритме каждый процессор отвечает за одну подматрицу C. В 3D-алгоритме каждая перемножаемая пара подматриц из A и B назначается одному процессору.

Алгоритмы, избегающие общения, и распределенные алгоритмы

В современных архитектурах с иерархической памятью стоимость загрузки и хранения элементов входной матрицы обычно превышает стоимость арифметических операций. На одной машине это объем данных, передаваемых между ОЗУ и кешем, а на многоузловой машине с распределенной памятью - это объем, передаваемый между узлами; в любом случае это называется полосой пропускания связи . Наивный алгоритм, использующий три вложенных цикла, использует полосу пропускания связи Ω( n ³ ) .

Алгоритм Кэннона , также известный как 2D-алгоритм , представляет собой алгоритм, позволяющий избежать связи, который разбивает каждую входную матрицу на блочную матрицу, элементы которой являются подматрицами размера √ M /3 на √ M /3 , где M — размер быстрой памяти. ^[25] Затем наивный алгоритм применяется к блочным матрицам, вычисляя произведения подматриц полностью в быстрой памяти. Это уменьшает пропускную способность связи до O ( n3 / √M ) ^{, что является асимптотически} оптимальным (для алгоритмов, выполняющих ^{вычисление} Ω( n3 ) . ^{[26] [27]}

В распределенной среде с p процессорами, расположенными в двумерной сетке √ p на √ p , каждому процессору может быть назначена одна подматрица результата, и произведение может быть вычислено с помощью каждого процессора, передающего O ( n ² / √ p ) слов, что является асимптотически оптимальным, если предположить, что каждый узел хранит минимум O ( n ² / p ) элементов. ^[27] Это можно улучшить с помощью 3D-алгоритма, который размещает процессоры в сетке 3D-куба, назначая каждый продукт двух входных подматриц одному процессору. Затем генерируются результирующие подматрицы путем сокращения каждой строки. ^[28] Этот алгоритм передает O ( n ² / p ^2/3 ) слов на процессор, что является асимптотически оптимальным. ^[27] Однако это требует репликации каждого элемента входной матрицы p ^1/3 раз, и поэтому требует в p ^1/3 больше памяти, чем необходимо для хранения входных данных. Этот алгоритм можно комбинировать с алгоритмом Штрассена для дальнейшего сокращения времени выполнения. ^[28] Алгоритмы «2.5D» обеспечивают постоянный компромисс между использованием памяти и пропускной способностью связи. ^[29] В современных распределенных вычислительных средах, таких как MapReduce , были разработаны специализированные алгоритмы умножения. ^[30]

Алгоритмы для сеток

Умножение матриц выполняется за 2n-1 шагов для двух матриц n×n в сетке с перекрестными связями.

Существует множество алгоритмов умножения на сетках . Для умножения двух n × n на стандартной двумерной сетке с использованием алгоритма 2D Кэннона можно выполнить умножение за 3 n -2 шага, хотя при повторных вычислениях это число сокращается вдвое. ^[31] Стандартный массив неэффективен, поскольку данные из двух матриц не поступают одновременно, и их необходимо дополнять нулями.

Результат еще быстрее на двухслойной сетке с перекрестными проволоками, где требуется всего 2 n -1 шагов. ^[32] Производительность еще больше улучшается при повторных вычислениях, что приводит к 100% эффективности. ^[33] Массив с перекрестной сеткой можно рассматривать как частный случай неплоской (т.е. многослойной) структуры обработки. ^[34]

Смотрите также

• Вычислительная сложность математических операций
• Вычислительная сложность умножения матриц
• Алгоритм CYK § Алгоритм Валианта
• Умножение цепочки матриц
• Умножение разреженной матрицы на вектор
• Метод четырех русских

Рекомендации

1. Скиена, Стивен (2012). «Сортировка и поиск». Руководство по проектированию алгоритмов . Спрингер. стр. 45–46, 401–3. дои : 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
2. Уильямс, Вирджиния Василевска; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Ренфэй (2024), Новые границы умножения матриц: от альфы до омеги , arXiv : 2307.07970
3. Дуань, Ран; У, Хунсюнь; Чжоу, Ренфэй (2022), Более быстрое умножение матриц посредством асимметричного хеширования , arXiv : 2210.10173
4. Алман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021), arXiv : 2010.05846
5. Хартнетт, Кевин (23 марта 2021 г.). «Умножение матрицы на несколько дюймов ближе к мифической цели». Журнал Кванта . Проверено 01 апреля 2021 г.
6. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 75–79. ISBN 0-262-03384-4.
7. Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Проектирование производительности программных систем, Лекция 8». MIT OpenCourseWare . Массачусетский Институт Технологий . Проверено 27 января 2015 г.
8. Лам, Моника С.; Ротберг, Эдвард Э.; Вольф, Майкл Э. (1991). Производительность кэша и оптимизация блокированных алгоритмов . ASPLOS91: 4-я Международная конференция по поддержке архитектуры языков программирования и операционных систем. дои : 10.1145/106972.106981. ISBN 978-0-89791-380-5.
9. Прокоп, Харальд (1999). Алгоритмы, не обращающие внимания на кэш (PDF) (магистр). Массачусетский технологический институт. hdl : 1721.1/80568.
10. Миллер, Уэбб (1975), «Вычислительная сложность и численная стабильность», SIAM News , 4 (2): 97–107, CiteSeerX 10.1.1.148.9947 , doi : 10.1137/0204009 
11. Пресс, Уильям Х.; Фланнери, Брайан П.; Теукольский, Саул А. ; Веттерлинг, Уильям Т. (2007). Численные рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета . п. 108. ИСБН 978-0-521-88068-8.
12. Штрассен, Волкер (1969). «Исключение по Гауссу не оптимально». Число. Математика . 13 (4): 354–356. дои : 10.1007/BF02165411. S2CID  121656251.
13. Виноград, Шмуэль (1971). «Об умножении матриц 2×2». Линейная алгебра и ее приложения . 4 (4): 381–388. дои : 10.1016/0024-3795(71)90009-7 .
14. Карштадт, Илай; Шварц, Одед (июль 2017 г.). «Умножение матриц, немного быстрее». Материалы 29-го симпозиума ACM по параллелизму в алгоритмах и архитектурах . СПАА '17. стр. 101–110. дои : 10.1145/3087556.3087579.
15. Проберт, Роберт Л. (1976). «Об аддитивной сложности умножения матриц». СИАМ Дж. Компьютер . 5 (2): 187–203. дои : 10.1137/0205016.
16. Бениамини, Гал; Ченг, Натан; Хольц, Ольга; Карштадт, Илай; Шварц, Одед (2020). «Разрежение операторов алгоритмов быстрого умножения матриц». arXiv : 2008.03759 [cs.DS].
17. Копперсмит, Дон; Виноград, Шмуэль (1990), «Умножение матриц посредством арифметических прогрессий» (PDF) , Журнал символических вычислений , 9 (3): 251, doi : 10.1016/S0747-7171(08)80013-2
18. Илиопулос, Костас С. (1989), «Оценки сложности в наихудшем случае для алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы» (PDF) , SIAM Journal on Computing , 18 ( 4): 658–669, CiteSeerX 10.1.1.531.9309 , doi : 10.1137/0218045, MR  1004789, заархивировано из оригинала (PDF) 05 марта 2014 г. , получено 16 января 2015 г. Алгоритм Копперсмита-Винограда: непрактично из-за очень большой скрытой константы в верхней границе необходимого количества умножений. 
19. Робинсон, Сара (ноябрь 2005 г.), «К оптимальному алгоритму умножения матриц» (PDF) , SIAM News , 38 (9), Даже если кому-то удастся доказать одну из гипотез, продемонстрировав тем самым, что ω = 2 — венок Продуктовый подход вряд ли будет применим к большим матричным проблемам, возникающим на практике. [...] входные матрицы должны быть астрономически большими, чтобы разница во времени была очевидна.
20. «Открытие новых алгоритмов с помощью AlphaTensor». www.deepmind.com . 5 октября 2022 г. Проверено 1 ноября 2022 г.
21. Фаузи, Аль-Хусейн; Балог, Матей; Хуанг, Аджа; Юбер, Томас; Ромера-Паредес, Бернардино; Барекатаин, Мохаммадамин; Новиков, Александр; Р. Руис, Франциско Дж.; Шритвизер, Джулиан; Свирщ, Гжегож; Сильвер, Дэвид; Хассабис, Демис; Кохли, Пушмит (октябрь 2022 г.). «Открытие более быстрых алгоритмов матричного умножения с помощью обучения с подкреплением». Природа . 610 (7930): 47–53. Бибкод : 2022Natur.610...47F. дои : 10.1038/s41586-022-05172-4. ISSN  1476-4687. ПМЦ 9534758 . ПМИД  36198780. 
22. Кауэрс, Мануэль; Моосбауэр, Якоб (2 декабря 2022 г.). «Перевернутые графы для умножения матриц». arXiv : 2212.01175 [cs.SC].
23. Брубейкер, Бен (23 ноября 2022 г.). «ИИ открывает новые возможности умножения матриц». Журнал Кванта . Проверено 26 ноября 2022 г.
24. Рэндалл, Кейт Х. (1998). Силк: Эффективные многопоточные вычисления (PDF) (доктор философии). Массачусетский Институт Технологий. стр. 54–57. hdl : 1721.1/47519.
25. Кэннон, Линн Эллиот (14 июля 1969 г.). Сотовый компьютер для реализации алгоритма фильтра Калмана (доктор философии). Государственный университет Монтаны.
26. Хонг, JW; Кунг, ХТ (1981). «Сложность ввода-вывода: игра с красно-синими камешками» (PDF) . Материалы тринадцатого ежегодного симпозиума ACM по теории вычислений - STOC '81 . стр. 326–333. дои : 10.1145/800076.802486. S2CID  8410593. Архивировано (PDF) из оригинала 15 декабря 2019 г.
27. Ирония, Дрор; Толедо, Сиван; Тискин, Александр (сентябрь 2004 г.). «Нижние границы связи для умножения матриц с распределенной памятью». Дж. Параллельное распределение. Вычислить . 64 (9): 1017–26. CiteSeerX 10.1.1.20.7034 . дои : 10.1016/j.jpdc.2004.03.021. 
28. Агарвал, RC; Балле, С.М.; Густавсон, ФГ; Джоши, М.; Палкар, П. (сентябрь 1995 г.). «Трехмерный подход к параллельному умножению матриц». IBM J. Res. Дев . 39 (5): 575–582. CiteSeerX 10.1.1.44.3404 . дои : 10.1147/rd.395.0575. 
29. Соломоник, Эдгар; Деммель, Джеймс (2011). «Оптимальные для связи параллельные алгоритмы умножения матриц 2.5D и LU-факторизации» (PDF) . Материалы 17-й Международной конференции по параллельной обработке . Том. Часть II. стр. 90–109. дои : 10.1007/978-3-642-23397-5_10. ISBN 978-3-642-23397-5.
30. Босаг Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от измерения, с использованием MapReduce» (PDF) . arXiv : 1304.1467 . Бибкод : 2013arXiv1304.1467B . Проверено 12 июля 2014 г.
31. Бэ, SE; Шинн, Т.-В.; Такаока, Т. (2014). «Более быстрый параллельный алгоритм умножения матриц в ячеистом массиве». Procedia Информатика . 29 : 22:30–40. дои : 10.1016/j.procs.2014.05.208 .
32. Как, С (1988). «Двухслойный сетчатый массив для умножения матриц». Параллельные вычисления . 6 (3): 383–5. CiteSeerX 10.1.1.88.8527 . дои : 10.1016/0167-8191(88)90078-6. 
33. Как, С. (2014). «Эффективность умножения матриц на массиве перекрестных ячеек». arXiv : 1411.3273 [cs.DC].
34. Как, С (1988). «Многослойные массивы вычислений». Информационные науки . 45 (3): 347–365. CiteSeerX 10.1.1.90.4753 . дои : 10.1016/0020-0255(88)90010-2. 

дальнейшее чтение

• Буттари, Альфредо; Лангу, Жюльен; Курзак, Якуб; Донгарра, Джек (2009). «Класс параллельных алгоритмов тайловой линейной алгебры для многоядерных архитектур». Параллельные вычисления . 35 : 38–53. arXiv : 0709.1272 . doi :10.1016/j.parco.2008.10.002. S2CID  955.
• Гото, Казусигэ; ван де Гейн, Роберт А. (2008). «Анатомия высокопроизводительного умножения матриц». Транзакции ACM в математическом программном обеспечении . 34 (3): 1–25. CiteSeerX  10.1.1.140.3583 . дои : 10.1145/1356052.1356053. S2CID  9359223.
• Ван Зи, Филд Г.; ван де Гейн, Роберт А. (2015). «BLIS: платформа для быстрого создания экземпляров функциональности BLAS». Транзакции ACM в математическом программном обеспечении . 41 (3): 1–33. дои : 10.1145/2764454. S2CID  1242360.
• Как оптимизировать GEMM