Алгоритм умножения матриц - Matrix multiplication algorithm

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

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

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

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

Непосредственное применение математического определения умножения матриц дает алгоритм, который занимает время в порядке $п 3$ умножить два $п \times п$ матрицы ( $Θ (п 3)$ в нотация большой O ). Лучшие асимптотические оценки времени, необходимого для умножения матриц, были известны со времен работы Штрассена в 1960-х годах, но до сих пор неизвестно, каково оптимальное время (т.е. сложность проблемы является).

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

В определение умножения матриц это если $C = AB$ для $п \times м$ матрица $А$ и $м \times п$ матрица $B$ , тогда $C$ является $п \times п$ матрица с записями

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

.

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

Вход: матрицы $А$ и $B$
Позволять $C$ быть новой матрицей подходящего размера
Для я от 1 до п:
- Для j от 1 до п:
  - Позволять $сумма = 0$
  - Для k от 1 до м:
    - Набор $сумма \leftarrow сумма + А ik \times B кДж$
  - Набор $C ij \leftarrow сумма$
Вернуть $C$

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

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

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

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

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

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

Вход: матрицы $А$ и $B$
Позволять $C$ быть новой матрицей подходящего размера
Выберите размер плитки $Т = Θ (\sqrt M)$
Для я от 1 до п в шагах от Т:
- Для J от 1 до п в шагах от Т:
  - Для K от 1 до м в шагах от Т:
    - Умножить $А я : я + Т, K : K + Т$ и $B K : K + Т, J : J + Т$ в $C я : я + Т, J : J + Т$ , это:
    - Для я от я к мин (я + Т, п):
      - Для $j$ от $J$ к $мин (J + Т, п)$ :
        Позволять $сумма = 0$
        Для $k$ от $K$ к $мин (K + Т, м)$ :
        Набор $сумма \leftarrow сумма + А ik \times B кДж$
        Набор $C ij \leftarrow C ij + сумма$
Вернуть $C$

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

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

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

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

,

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

{displaystyle {egin {pmatrix} C_ {11} & C_ {12} C_ {21} & C_ {22} end {pmatrix}} = {egin {pmatrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {pmatrix}} {egin {pmatrix} B_ {11} & B_ {12} B_ {21} & B_ {22} end {pmatrix}} = {egin {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 = а 11 б 11$ в качестве базового случая.

Сложность этого алгоритма в зависимости от $п$ дается повторением^[2]

{displaystyle T (1) = Theta (1)}

;

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

,

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

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

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

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

Если $Максимум(п, м, п) = п$ , Трещина $А$ горизонтально:

{displaystyle C = {egin {pmatrix} A_ {1} A_ {2} end {pmatrix}} {B} = {egin {pmatrix} A_ {1} B A_ {2} Bend {pmatrix}}}

Иначе, если $Максимум(п, м, п) = п$ , Трещина $B$ вертикально:

{displaystyle C = A {egin {pmatrix} B_ {1} & B_ {2} end {pmatrix}} = {egin {pmatrix} AB_ {1} & AB_ {2} end {pmatrix}}}

В противном случае, $Максимум(п, м, п) = м$ . Трещина $А$ вертикально и $B$ горизонтально:

{displaystyle C = {egin {pmatrix} A_ {1} & A_ {2} end {pmatrix}} {egin {pmatrix} B_ {1} B_ {2} end {pmatrix}} = A_ {1} B_ {1} + A_ {2} B_ {2}}

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

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

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

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

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

Низший

ω

такое, что умножение матриц, как известно,

О (п ω)

, построенный против времени.

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

Электрический ток $О (п k)$ алгоритм с наименьшим известным показателем $k$ является обобщением Алгоритм Копперсмита – Винограда имеющая асимптотическую сложность $О (п 2.3728639)$ , автор Франсуа Ле Галль.^[8] Алгоритм Ле Галля и алгоритм Копперсмита – Винограда, на котором он основан, похожи на алгоритм Штрассена: изобретен способ умножения двух $k \times k$ -матрицы с числом меньше $k 3$ умножения, и этот метод применяется рекурсивно. Однако постоянный коэффициент, скрытый Обозначение Big O настолько велик, что эти алгоритмы имеют смысл только для матриц, которые слишком велики для обработки на современных компьютерах.^[9]^[10]

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

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

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

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

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

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

{displaystyle {egin {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}}}

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

Процедура $умножить (C, А, B)$ :

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

Процедура $Добавить(C, Т)$ добавляет $Т$ в $C$ , поэлементно:

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

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

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

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

C

. В 3D-алгоритме каждая пара подматриц из

А

и

B

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

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

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

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

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

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

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

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

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

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

использованная литература

^ ^а ^б ^c ^d Скиена, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов. Springer. стр.45 –46, 401–403. Дои:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
^ ^а ^б ^c Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. С. 75–79. ISBN 0-262-03384-4.
^ ^а ^б ^c ^d ^е Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Инженерия производительности программных систем, лекция 8». MIT OpenCourseWare. Массачусетский Институт Технологий. Получено 27 января 2015.
^ Lam, Monica S .; Ротберг, Эдвард Э .; Вольф, Майкл Э. (1991). Производительность кеша и оптимизация заблокированных алгоритмов. Международная конф. по архитектурной поддержке языков программирования и операционных систем (ASPLOS).
^ ^а ^б ^c Прокоп, Харальд (1999). Алгоритмы, не обращающие внимания на кеш (PDF) (Магистратура). Массачусетский технологический институт.
^ Миллер, Уэбб (1975), "Вычислительная сложность и численная устойчивость", Новости SIAM, 4 (2): 97–107, CiteSeerX 10.1.1.148.9947, Дои:10.1137/0204009
^ Press, William H .; Флэннери, Брайан П .; Теукольский, Саул А.; Веттерлинг, Уильям Т. (2007). Числовые рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета. п.108. ISBN 978-0-521-88068-8.
^ Ле Галл, Франсуа (2014), «Степени тензоров и быстрое матричное умножение», Материалы 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014), arXiv:1401.7714, Bibcode:2014arXiv1401.7714L. Оригинальный алгоритм был представлен Дон Копперсмит и Шмуэль Виноград в 1990 г. имеет асимптотическую сложность $О (п 2.376)$ . В 2013 году он был улучшен до $О (п 2.3729)$ от Вирджиния Василевска Уильямс, что дает время лишь немного хуже, чем улучшение Ле Галля: Уильямс, Вирджиния Василевска. «Умножение матриц быстрее, чем Копперсмит-Виноград» (PDF).
^ Илиопулос, Костас С. (1989), «Границы сложности в наихудшем случае алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы» (PDF), SIAM Журнал по вычислениям, 18 (4): 658–669, CiteSeerX 10.1.1.531.9309, Дои:10.1137/0218045, Г-Н 1004789, заархивировано из оригинал (PDF) на 2014-03-05, получено 2015-01-16, Алгоритм Копперсмита – Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений.
^ ^а ^б Робинсон, Сара (2005). «К оптимальному алгоритму умножения матриц» (PDF). Новости SIAM. 38 (9).
^ Раз, Ран (2002). «О сложности матричного произведения». Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений: 144. Дои: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.
^ Алон, Шпилка, Уманс, О подсолнухах и матричном умножении
^ ^а ^б Рэндалл, Кейт Х. (1998). Cilk: эффективные многопоточные вычисления (PDF) (Кандидат наук.). Массачусетский Институт Технологий. С. 54–57.
^ Линн Эллиот Кэннон, Сотовый компьютер для реализации алгоритма фильтра Калмана, Технический отчет, к.т.н. Диссертация, Государственный университет Монтаны, 14 июля 1969 г.
^ Hong, J. W .; Кунг, Х. Т. (1981). «Сложность ввода-вывода: игра с красно-синей галькой» (PDF). STOC '81: Материалы тринадцатого ежегодного симпозиума ACM по теории вычислений: 326–333.
^ ^а ^б ^c Ирония, Дрор; Толедо, Сиван; Тискин, Александр (сентябрь 2004 г.). «Нижние границы связи для умножения матриц с распределенной памятью». J. Parallel Distrib. Вычислить. 64 (9): 1017–1026. CiteSeerX 10.1.1.20.7034. Дои:10.1016 / j.jpdc.2004.03.021.
^ ^а ^б Agarwal, R.C .; Balle, S.M .; Густавсон, Ф. Г .; Джоши, М .; Палкар П. (сентябрь 1995 г.). «Трехмерный подход к параллельному умножению матриц». IBM J. Res. Dev. 39 (5): 575–582. CiteSeerX 10.1.1.44.3404. Дои:10.1147 / rd.395.0575.
^ Соломоник, Эдгар; Деммель, Джеймс (2011). "Коммуникационно-оптимальные параллельные алгоритмы умножения матриц 2.5D и факторизации LU". Материалы 17-й Международной конференции по параллельной обработке. Часть II: 90–109.
^ Босах Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от размеров с использованием MapReduce» (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Получено 12 июля 2014. Цитировать журнал требует | журнал = (Помогите)
^ Bae, S.E .; Shinn, T.-W .; Такаока, Т. (2014). «Более быстрый параллельный алгоритм умножения матриц на сеточном массиве». Процедуры информатики. 29: 2230–2240. Дои:10.1016 / j.procs.2014.05.208.
^ Как, S (1988). «Двухслойная сетка для умножения матриц». Параллельные вычисления. 6 (3): 383–385. CiteSeerX 10.1.1.88.8527. Дои: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. Дои:10.1016/0020-0255(88)90010-2.

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

Буттари, Альфредо; Лангу, Жюльен; Курзак, Якуб; Донгарра, Джек (2009). «Класс параллельных мозаичных алгоритмов линейной алгебры для многоядерных архитектур». Параллельные вычисления. 35: 38–53. arXiv:0709.1272. Дои: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.
Van Zee, Field G .; ван де Гейн, Роберт А. (2015). «BLIS: структура для быстрого создания экземпляра функциональности BLAS». Транзакции ACM на математическом ПО. 41 (3): 1–33. Дои:10.1145/2764454. S2CID 1242360.
Как оптимизировать GEMM

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

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

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

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

[prokop-5] а ^б ^c Прокоп, Харальд (1999). Алгоритмы, не обращающие внимания на кеш (PDF) (Магистратура). Массачусетский технологический институт.

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

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

[8] Ле Галл, Франсуа (2014), «Степени тензоров и быстрое матричное умножение», Материалы 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014), arXiv:1401.7714, Bibcode:2014arXiv1401.7714L. Оригинальный алгоритм был представлен Дон Копперсмит и Шмуэль Виноград в 1990 г. имеет асимптотическую сложность $О (п 2.376)$ . В 2013 году он был улучшен до $О (п 2.3729)$ от Вирджиния Василевска Уильямс, что дает время лишь немного хуже, чем улучшение Ле Галля: Уильямс, Вирджиния Василевска. «Умножение матриц быстрее, чем Копперсмит-Виноград» (PDF).

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

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

[11] Раз, Ран (2002). «О сложности матричного произведения». Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений: 144. Дои: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). Cilk: эффективные многопоточные вычисления (PDF) (Кандидат наук.). Массачусетский Институт Технологий. С. 54–57.

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

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

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

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

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

[21] Босах Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от размеров с использованием MapReduce» (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Получено 12 июля 2014. Цитировать журнал требует | журнал = (Помогите)

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

[23] Как, S (1988). «Двухслойная сетка для умножения матриц». Параллельные вычисления. 6 (3): 383–385. CiteSeerX 10.1.1.88.8527. Дои: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. Дои:10.1016/0020-0255(88)90010-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

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