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

Нерешенная проблема в информатике :

Какой алгоритм умножения матриц самый быстрый?

(больше нерешенных проблем в информатике)

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

Непосредственное применение математического определения умножения матриц дает алгоритм, который требует времени порядка $n 3$ полевых операций для умножения двух матриц размера $n \times n$ над этим полем ( $Θ (n 3)$ в нотации большой O ). Лучшие асимптотические оценки времени, необходимого для умножения матриц, были известны со времен алгоритма Штрассена в 1960-х годах, но до сих пор неизвестно, каково оптимальное время (т. Е. Какова сложность проблемы ). По состоянию на декабрь 2020 ^{[Обновить]}года алгоритм умножения матриц с наилучшей асимптотической сложностью работает за $O (n 2.3728596)$ время, данное Джошем Алманом и Вирджинией Василевской Уильямс ,^[2] однако этот алгоритм является галактическим алгоритмом из-за больших констант и не может быть реализован практически.

Итерационный алгоритм [ править ]

Определение матричного умножения является то , что если $С = АВ$ для $п \times м$ матрицы $А$ и $м \times р$ матрицы $B$ , то $С$ является $п \times р$ матрица с элементами

{\ 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 :
  - Пусть $sum = 0$
  - Для k от 1 до m :
    - Установить $сумму \leftarrow сумма + A ik \times B kj$
  - Установить $C ij \leftarrow sum$
Возврат $C$

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

Поведение кеша [ править ]

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

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

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

Оптимальным вариантом итерационного алгоритма для $A$ и $B$ в строковой компоновке является мозаичная версия, где матрица неявно делится на квадратные плитки размером $\sqrt M$ на $\sqrt M$ : ^[4]^[5]

Вход: матрицы $A$ и $B$
Пусть $C$ - новая матрица подходящего размера
Выберите размер плитки $T = Θ (\sqrt 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)$ :
        Пусть $sum = 0$
        Для $k$ от $K$ до $min (K + T, m)$ :
        Установить $сумму \leftarrow сумма + A ik \times B kj$
        Положим $C ij \leftarrow C ij + sum$
Возврат $C$

В идеализированной модели кэша этот алгоритм требует только $Θ (п 3 / б \sqrt M)$ промахи в кэше; делитель $b \sqrt M$ составляет несколько порядков на современных машинах, так что фактические вычисления преобладают во времени выполнения, а не в пропусках кэша. ^[4]

Алгоритм разделяй и властвуй [ править ]

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

{\ 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} \\\ конец {pmatrix}}}

,

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

{\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 11 = a 11 b 11$ .

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

T(1)=\Theta (1)

;

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

,

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

Неквадратные матрицы [ править ]

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

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

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

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 по$ вертикали:

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 по$ горизонтали:

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}

Поведение кеша [ править ]

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

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

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

Субкубические алгоритмы [ править ]

Улучшение оценок показателя

ω

со временем для вычислительной сложности умножения матриц .

O(n^{\omega })

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

В теоретической информатике остается открытым вопрос, насколько хорошо можно улучшить алгоритм Штрассена. Показатель умножения матриц - это наименьшее действительное число, для которого любая матрица над полем может быть умножена вместе с помощью полевых операций. На данный момент лучший результат - 2.3728596, сделанный Джошем Алманом и Вирджинией Василевской Уильямс . ^[2] Этот алгоритм, как и все другие недавние алгоритмы в этом направлении исследований, является обобщением алгоритма Копперсмита – Винограда , который был дан Доном Копперсмитом и Шмуэлем Виноградом в 1990 году, и имеет асимптотическую сложность $O$ $($ $n$ $\omega$ $n\times n$ $n^{\omega +o(1)}$ $\omega$ $2.376)$ . Концептуальная идея этих алгоритмов аналогична алгоритму Штрассена: разработан способ умножения двух $k \times k$ -матриц с менее чем $k 3$ умножениями, и этот метод применяется рекурсивно. Однако постоянный коэффициент, скрытый обозначением Big O, настолько велик, что эти алгоритмы подходят только для матриц, которые слишком велики для обработки на современных компьютерах.^[9]^[10]

Поскольку любой алгоритм умножения двух матриц $размера$ $n \times n$ должен обрабатывать все $2 n 2$ элементов, существует асимптотическая нижняя граница операций $Ω (n 2)$ . Раз доказал нижнюю границу $Ω (n 2 log (n))$ для арифметических схем с ограниченными коэффициентами над действительными или комплексными числами. ^[11]

Cohn et al. поместите такие методы, как алгоритмы Штрассена и Копперсмита – Винограда, в совершенно другой теоретико-групповой контекст, используя тройки подмножеств конечных групп, которые удовлетворяют свойству дизъюнктности, называемому свойством тройного произведения (TPP) . Они показывают , что если семьи сплетений из абелевых групп с симметричными группами понимают семейство подмножеств троек с одновременной версией ТЭС, то есть алгоритмы умножения матриц с существенно квадратичной сложностью. ^[12]^[13] Большинство исследователей считают, что это действительно так. ^[10] Однако Алон, Шпилка и Крис Уманснедавно показали, что некоторые из этих гипотез, предполагающих быстрое матричное умножение, несовместимы с другой правдоподобной гипотезой - гипотезой о подсолнечнике . ^[14]

Алгоритм Фрейвальдс представляет собой простой алгоритм Монте - Карло , что с учетом матрицы , $B$ и $C$ , проверяет , в $Q ($ $п$ $2$ $)$ время , если $AB$ $=$ $C$ .

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

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

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

{\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}}

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

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

Базовый случай: если $n = 1$ , установить $c 11 \leftarrow a 11 \times b 11$ (или умножить маленькую блочную матрицу).
В противном случае выделите место для новой матрицы T формы n × n , тогда:
- Разделите $A$ на $A 11$ , $A 12$ , $A 21$ , $A 22$ .
- Разделите $B$ на $B 11$ , $B 12$ , $B 21$ , $B 22$ .
- Разделите $C$ на $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Разделите $Т$ на $Т 11$ , $Т 12$ , $Т 21$ , $Т 22$ .
- Параллельное исполнение:
  - Вилкой $умножаем (C 11, A 11, B 11)$ .
  - Вилкой $умножаем (C 12, A 11, B 12)$ .
  - Вилкой $умножаем (C 21, A 21, B 11)$ .
  - Вилкой $умножаем (C 22, A 21, B 12)$ .
  - Вилкой $умножаем (Т 11, А 12, В 21)$ .
  - Вилкой $умножаем (Т 12, А 12, В 22)$ .
  - Вилкой $умножаем (Т 21, А 22, В 21)$ .
  - Вилкой $умножаем (Т 22, А 22, В 22)$ .
- Присоединяйтесь (дождитесь завершения параллельных вилок).
- $добавить (C, T)$ .
- Освобождает $Т$ .

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

Базовый случай: если $n = 1$ , установите $c 11 \leftarrow c 11 + t 11$ (или сделайте короткий цикл, возможно, развернутый).
Иначе:
- Разделите $C$ на $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- Разделите $Т$ на $Т 11$ , $Т 12$ , $Т 21$ , $Т 22$ .
- В параллели:
  - Вилка $добавить (C 11, T 11)$ .
  - Вилка $добавочная (C 12, T 12)$ .
  - Вилка $добавить (C 21, T 21)$ .
  - Вилка $добавочная (C 22, T 22)$ .
- Присоединяйтесь .

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

Этот алгоритм имеет критическую длину пути из $Q (журнал 2 п)$ шагов, а это означает , что нужно так много времени на идеальной машине с бесконечным числом процессоров; Таким образом, она имеет максимально возможное ускорение из $Q (п 3 / войти 2 п)$ на любом реальном компьютере. Алгоритм непрактичен из-за затрат на обмен данными, связанных с перемещением данных во временную матрицу $T$ и из нее , но более практичный вариант обеспечивает ускорение $(n 2)$ без использования временной матрицы. ^[15]

Блочное умножение матриц. В алгоритме 2D, каждый процессор отвечает за один подматрицы

C

. В трехмерном алгоритме каждая умноженная пара подматриц из

A

и

B

назначается одному процессору.

Распределенные алгоритмы избегания общения [ править ]

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

Алгоритм Кэннона , также известный как 2D-алгоритм , представляет собой алгоритм избегания связи, который разбивает каждую входную матрицу на блочную матрицу, элементы которой являются подматрицами размера $\sqrt M / 3$ на $\sqrt M / 3$ , где $M$ - размер быстрой памяти. ^[16] Затем наивный алгоритм используется над блочными матрицами, вычисляя продукты подматриц полностью в быстрой памяти. Это уменьшает пропускную способность связи до $O (n 3 / \sqrt M)$ , что является асимптотически оптимальным (для алгоритмов, выполняющих $Ω (n 3)$ вычисление). ^[17]^[18]

В распределенной настройке с $p$ процессорами, расположенными в двумерной сетке $\sqrt p$ на $\sqrt p$ , одна подматрица результата может быть назначена каждому процессору, и произведение может быть вычислено с каждым процессором, передающим $O (n 2 / \sqrt p)$ слов, что является асимптотически оптимальным при условии, что каждый узел хранит минимум $O (n 2 / p)$ элементов. ^[18] Это можно улучшить с помощью 3D-алгоритма,который объединяет процессоры в трехмерную кубическую сетку, назначая каждое произведение двух входных подматриц одному процессору. Затем подматрицы результатов генерируются путем сокращения по каждой строке. ^[19] Этот алгоритм передает $O (n 2 / p 2/3)$ слов на процессор, что является асимптотически оптимальным. ^[18] Однако это требует дублирования каждого элемента входной матрицы $p 1/3$ раза, а значит, требует в $p 1/3$ больше памяти, чем требуется для хранения входных данных. Этот алгоритм можно комбинировать с Strassen для дальнейшего сокращения времени выполнения. ^[19]Алгоритмы «2.5D» обеспечивают постоянный компромисс между использованием памяти и пропускной способностью связи. ^[20] В современных распределенных вычислительных средах, таких как MapReduce , были разработаны специализированные алгоритмы умножения. ^[21]

Алгоритмы для сеток [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ a b c d Скиена, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов . Springer. стр. 45 -46, 401-403. DOI : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
^ а б Альман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021) , arXiv : 2010.05846
^ a b c Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. С. 75–79. ISBN 0-262-03384-4.
^ a b c d e Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Инженерия производительности программных систем, лекция 8» . MIT OpenCourseWare . Массачусетский технологический институт . Проверено 27 января 2015 года .
^ Лам, Моника S .; Ротберг, Эдвард Э .; Вольф, Майкл Э. (1991). Производительность кеша и оптимизация заблокированных алгоритмов . Междунар. Конф. по архитектурной поддержке языков программирования и операционных систем (ASPLOS).
^ a b c Прокоп, Харальд (1999). Cache-Oblivious Algorithms (PDF) (Магистр). Массачусетский технологический институт.
^ Миллер, Уэбб (1975), "Вычислительная сложность и устойчивость численного", SIAM Новости , 4 (2): 97-107, CiteSeerX 10.1.1.148.9947 , DOI : 10,1137 / 0204009
^ Press, Уильям Х .; Фланнери, Брайан П .; Теукольский, Саул А .; Веттерлинг, Уильям Т. (2007). Числовые рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета . п. 108 . ISBN 978-0-521-88068-8.
^ Илиопулос, Костас С. (1989), "Границы сложности в наихудшем случае алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы" (PDF) , SIAM Journal on Computing , 18 ( 4): 658-669, CiteSeerX 10.1.1.531.9309 , DOI : 10,1137 / 0218045 , MR 1004789 , архивируются с оригинала (PDF) на 2014-03-05 , извлекаться 2015-01-16 , Алгоритм Копперсмита – Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений.
^ a b Робинсон, Сара (2005). «К оптимальному алгоритму умножения матриц» (PDF) . Новости SIAM . 38 (9).
Перейти ↑ Raz, Ran (2002). «О сложности матричного произведения». Труды тридцать четвертый ежегодный ACM симпозиум по теории вычислений : 144. DOI : 10,1145 / 509907.509932 . ISBN 1581134959. S2CID 9582328 .
^ Генри Кон, Роберт Кляйнберг , Балаж Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. arXiv : math.GR/0511460 . Материалы 46-го ежегодного симпозиума по основам компьютерных наук , 23–25 октября 2005 г., Питтсбург, Пенсильвания, IEEE Computer Society, стр. 379–388.
^ Генри Кон, Крис Уманс. Теоретико-групповой подход к быстрому умножению матриц. arXiv : math.GR/0307321 . Материалы 44-го ежегодного симпозиума IEEE по основам компьютерных наук , 11–14 октября 2003 г., Кембридж, Массачусетс, Компьютерное общество IEEE, стр. 438–449.
^ Алон , Шпилка, Уманс, О подсолнухах и матричном умножении
^ a b Рэндалл, Кейт Х. (1998). Силк: Эффективные многопоточные вычисления (PDF) (доктор философии). Массачусетский Институт Технологий. С. 54–57.
^ Линн Эллиот Кэннон, сотовый компьютер для реализации алгоритма фильтра Калмана , технический отчет, доктор философии. Диссертация, Государственный университет Монтаны, 14 июля 1969 г.
^ Хонг, JW; Кунг, HT (1981). «Сложность ввода-вывода: игра с красно-синей галькой» (PDF) . STOC '81: Материалы тринадцатого ежегодного симпозиума ACM по теории вычислений : 326–333.
^ a b c Ирония, Дрор; Толедо, Сиван; Тискин, Александр (сентябрь 2004 г.). «Нижние границы связи для умножения матриц распределенной памяти». J. Parallel Distrib. Comput . 64 (9): 1017–1026. CiteSeerX 10.1.1.20.7034 . DOI : 10.1016 / j.jpdc.2004.03.021 .
^ a b Agarwal, RC; Balle, SM; Густавсон, Ф.Г .; Джоши, М .; Палкар П. (сентябрь 1995 г.). «Трехмерный подход к параллельному умножению матриц». IBM J. Res. Dev . 39 (5): 575–582. CiteSeerX 10.1.1.44.3404 . DOI : 10.1147 / rd.395.0575 .
^ Соломоник, Эдгар; Деммель, Джеймс (2011). "Коммуникационно-оптимальные параллельные алгоритмы умножения матриц 2.5D и факторизации LU". Материалы 17-й Международной конференции по параллельной обработке . Часть II: 90–109.
^ Bosagh зад, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от размеров с использованием MapReduce» (PDF) . arXiv : 1304,1467 . Bibcode : 2013arXiv1304.1467B . Проверено 12 июля 2014 . Cite journal requires |journal= (help)
^ Bae, SE; Shinn, T.-W .; Такаока, Т. (2014). «Более быстрый параллельный алгоритм умножения матриц на сеточном массиве» . Процедуры информатики . 29 : 2230–2240. DOI : 10.1016 / j.procs.2014.05.208 .
^ Как, S (1988). «Двухслойная сетка для умножения матриц». Параллельные вычисления . 6 (3): 383–385. CiteSeerX 10.1.1.88.8527 . DOI : 10.1016 / 0167-8191 (88) 90078-6 .
^ Как, С. (2014) Эффективность умножения матриц на сеточном массиве с перекрестной связью. https://arxiv.org/abs/1411.3273
^ Как, S (1988). «Многослойные массивы вычислений». Информационные науки . 45 (3): 347–365. CiteSeerX 10.1.1.90.4753 . DOI : 10.1016 / 0020-0255 (88) 90010-2 .

Дальнейшее чтение [ править ]

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

[skiena-1] Скиена, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов . Springer. стр. 45 -46, 401-403. DOI : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.

[aw20-2] а б Альман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021) , arXiv : 2010.05846

[clrs-3] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. С. 75–79. ISBN 0-262-03384-4.

[ocw-4] Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Инженерия производительности программных систем, лекция 8» . MIT OpenCourseWare . Массачусетский технологический институт . Проверено 27 января 2015 года .

[5] Лам, Моника S .; Ротберг, Эдвард Э .; Вольф, Майкл Э. (1991). Производительность кеша и оптимизация заблокированных алгоритмов . Междунар. Конф. по архитектурной поддержке языков программирования и операционных систем (ASPLOS).

[prokop-6] Прокоп, Харальд (1999). Cache-Oblivious Algorithms (PDF) (Магистр). Массачусетский технологический институт.

[7] Миллер, Уэбб (1975), "Вычислительная сложность и устойчивость численного", SIAM Новости , 4 (2): 97-107, CiteSeerX 10.1.1.148.9947 , DOI : 10,1137 / 0204009

[8] Press, Уильям Х .; Фланнери, Брайан П .; Теукольский, Саул А .; Веттерлинг, Уильям Т. (2007). Числовые рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета . п. 108 . ISBN 978-0-521-88068-8.

[9] Илиопулос, Костас С. (1989), "Границы сложности в наихудшем случае алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы" (PDF) , SIAM Journal on Computing , 18 ( 4): 658-669, CiteSeerX 10.1.1.531.9309 , DOI : 10,1137 / 0218045 , MR 1004789 , архивируются с оригинала (PDF) на 2014-03-05 , извлекаться 2015-01-16 , Алгоритм Копперсмита – Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений.

[robinson-10] Робинсон, Сара (2005). «К оптимальному алгоритму умножения матриц» (PDF) . Новости SIAM . 38 (9).

[11] Перейти ↑ Raz, Ran (2002). «О сложности матричного произведения». Труды тридцать четвертый ежегодный ACM симпозиум по теории вычислений : 144. DOI : 10,1145 / 509907.509932 . ISBN 1581134959. S2CID 9582328 .

[12] Генри Кон, Роберт Кляйнберг , Балаж Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. arXiv : math.GR/0511460 . Материалы 46-го ежегодного симпозиума по основам компьютерных наук , 23–25 октября 2005 г., Питтсбург, Пенсильвания, IEEE Computer Society, стр. 379–388.

[13] Генри Кон, Крис Уманс. Теоретико-групповой подход к быстрому умножению матриц. arXiv : math.GR/0307321 . Материалы 44-го ежегодного симпозиума IEEE по основам компьютерных наук , 11–14 октября 2003 г., Кембридж, Массачусетс, Компьютерное общество IEEE, стр. 438–449.

[14] Алон , Шпилка, Уманс, О подсолнухах и матричном умножении

[cilk-15] Рэндалл, Кейт Х. (1998). Силк: Эффективные многопоточные вычисления (PDF) (доктор философии). Массачусетский Институт Технологий. С. 54–57.

[16] Линн Эллиот Кэннон, сотовый компьютер для реализации алгоритма фильтра Калмана , технический отчет, доктор философии. Диссертация, Государственный университет Монтаны, 14 июля 1969 г.

[17] Хонг, JW; Кунг, HT (1981). «Сложность ввода-вывода: игра с красно-синей галькой» (PDF) . STOC '81: Материалы тринадцатого ежегодного симпозиума ACM по теории вычислений : 326–333.

[irony-18] Ирония, Дрор; Толедо, Сиван; Тискин, Александр (сентябрь 2004 г.). «Нижние границы связи для умножения матриц распределенной памяти». J. Parallel Distrib. Comput . 64 (9): 1017–1026. CiteSeerX 10.1.1.20.7034 . DOI : 10.1016 / j.jpdc.2004.03.021 .

[Agarwal-19] Agarwal, RC; Balle, SM; Густавсон, Ф.Г .; Джоши, М .; Палкар П. (сентябрь 1995 г.). «Трехмерный подход к параллельному умножению матриц». IBM J. Res. Dev . 39 (5): 575–582. CiteSeerX 10.1.1.44.3404 . DOI : 10.1147 / rd.395.0575 .

[20] Соломоник, Эдгар; Деммель, Джеймс (2011). "Коммуникационно-оптимальные параллельные алгоритмы умножения матриц 2.5D и факторизации LU". Материалы 17-й Международной конференции по параллельной обработке . Часть II: 90–109.

[21] Bosagh зад, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от размеров с использованием MapReduce» (PDF) . arXiv : 1304,1467 . Bibcode : 2013arXiv1304.1467B . Проверено 12 июля 2014 . Cite journal requires |journal= (help)

[22] Bae, SE; Shinn, T.-W .; Такаока, Т. (2014). «Более быстрый параллельный алгоритм умножения матриц на сеточном массиве» . Процедуры информатики . 29 : 2230–2240. DOI : 10.1016 / j.procs.2014.05.208 .

[23] Как, S (1988). «Двухслойная сетка для умножения матриц». Параллельные вычисления . 6 (3): 383–385. CiteSeerX 10.1.1.88.8527 . DOI : 10.1016 / 0167-8191 (88) 90078-6 .

[24] Как, С. (2014) Эффективность умножения матриц на сеточном массиве с перекрестной связью. https://arxiv.org/abs/1411.3273

[25] Как, S (1988). «Многослойные массивы вычислений». Информационные науки . 45 (3): 347–365. CiteSeerX 10.1.1.90.4753 . DOI : 10.1016 / 0020-0255 (88) 90010-2 .

[1]

vтеЧисленная линейная алгебра
Ключевые идеи	Плавающая точка Численная стабильность
Проблемы	Система линейных уравнений Матричные разложения Умножение матриц ( алгоритмы ) Расщепление матрицы Редкие проблемы
Аппаратное обеспечение	Кеш процессора TLB Алгоритм без кеширования SIMD Многопроцессорность
Программного обеспечения	MATLAB Подпрограммы базовой линейной алгебры (BLAS) ЛАПАК Специализированные библиотеки Программное обеспечение общего назначения