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

Нерешенная проблема в информатике: Какой алгоритм умножения матриц самый быстрый? (больше нерешенных проблем в информатике)

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

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

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

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

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

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

• Вход: матрицы А и B
• Позволять C быть новой матрицей подходящего размера
• Для я от 1 до п:
  • Для j от 1 до п:
    • Позволять сумма = 0
    • Для k от 1 до м:
      • Набор сумма ← сумма + А_ik × B_кДж
    • Набор C_ij ← сумма
• Вернуть C

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

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

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

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

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

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

• Вход: матрицы А и B
• Позволять C быть новой матрицей подходящего размера
• Выберите размер плитки Т = Θ (√M)
• Для я от 1 до п в шагах от Т:
  • Для J от 1 до п в шагах от Т:
    • Для K от 1 до м в шагах от Т:
      • Умножить А_{я:я+Т, K:K+Т} и B_{K:K+Т, J:J+Т} в C_{я:я+Т, J:J+Т}, это:
      • Для я от я к мин (я + Т, п):
        • Для j от J к мин (J + Т, п):
          • Позволять сумма = 0
          • Для k от K к мин (K + Т, м):
            • Набор сумма ← сумма + А_ik × B_кДж
          • Набор C_ij ← C_ij + сумма
• Вернуть C

В идеализированной модели кэша этот алгоритм требует только Θ (п³/б √M) промахи в кэше; делитель б √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^п × 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₁₁ = а₁₁б₁₁ в качестве базового случая.

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

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

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

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

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

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

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

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

${displaystyle C={egin{pmatrix}A_{1}A_{2}end{pmatrix}}{B}={egin{pmatrix}A_{1}BA_{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 × 2-матрицы, требующие всего 7 умножений (вместо обычных 8) за счет нескольких дополнительных операций сложения и вычитания. Рекурсивное применение этого алгоритма дает алгоритм с мультипликативной стоимостью ${displaystyle O(n^{log _{2}7})approx O(n^{2.807})}$. Алгоритм Штрассена более сложен, и числовая стабильность уменьшается по сравнению с наивным алгоритмом,^[6]но это быстрее в случаях, когда п > 100 или так^[1] и присутствует в нескольких библиотеках, таких как BLAS.^[7] Это очень полезно для больших матриц в точных областях, таких как конечные поля, где числовая стабильность не является проблемой.

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

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

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

Алгоритм Фрейвальдса это простой Алгоритм Монте-Карло что, учитывая матрицы А, B и C, проверяет в Θ (п²) время, если 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₁₁ ← а₁₁ × б₁₁ (или умножьте небольшую блочную матрицу).
• В противном случае выделите место для новой матрицы Т формы п × п, тогда:
  • Раздел А в А₁₁, А₁₂, А₂₁, А₂₂.
  • Раздел B в B₁₁, B₁₂, B₂₁, B₂₂.
  • Раздел C в C₁₁, C₁₂, C₂₁, C₂₂.
  • Раздел Т в Т₁₁, Т₁₂, Т₂₁, Т₂₂.
  • Параллельное исполнение:
    • Вилка умножить (C₁₁, А₁₁, B₁₁).
    • Вилка умножить (C₁₂, А₁₁, B₁₂).
    • Вилка умножить (C₂₁, А₂₁, B₁₁).
    • Вилка умножить (C₂₂, А₂₁, B₁₂).
    • Вилка умножить (Т₁₁, А₁₂, B₂₁).
    • Вилка умножить (Т₁₂, А₁₂, B₂₂).
    • Вилка умножить (Т₂₁, А₂₂, B₂₁).
    • Вилка умножить (Т₂₂, А₂₂, B₂₂).
  • Присоединиться (дождитесь завершения параллельных вилок).
  • Добавить(C, Т).
  • Освободить Т.

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

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

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

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

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

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

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

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

В распределенной среде с п процессоры расположены в √п от √п 2D-сетка, одна подматрица результата может быть назначена каждому процессору, и произведение может быть вычислено с каждым процессором, передающим О(п²/√п) слов, что является асимптотически оптимальным при условии, что каждый узел хранит минимум О(п²/п) элементы.^[18] Это можно улучшить с помощью 3D алгоритм, который объединяет процессоры в трехмерную кубическую сетку, назначая каждое произведение двух входных подматриц одному процессору. Затем подматрицы результатов генерируются путем сокращения по каждой строке.^[19] Этот алгоритм передает О(п²/п^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]

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

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

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

1. Скиена, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов. Springer. стр.45 –46, 401–403. Дои:10.1007/978-1-84800-070-4_4. ISBN  978-1-84800-069-8.
2. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. С. 75–79. ISBN  0-262-03384-4.
3. Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Инженерия производительности программных систем, лекция 8». MIT OpenCourseWare. Массачусетский Институт Технологий. Получено 27 января 2015.
4. Lam, Monica S .; Ротберг, Эдвард Э .; Вольф, Майкл Э. (1991). Производительность кеша и оптимизация заблокированных алгоритмов. Международная конф. по архитектурной поддержке языков программирования и операционных систем (ASPLOS).
5. Прокоп, Харальд (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, Алгоритм Копперсмита – Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений.
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. Алон, Шпилка, Уманс, О подсолнухах и матричном умножении
15. Рэндалл, Кейт Х. (1998). Cilk: эффективные многопоточные вычисления (PDF) (Кандидат наук.). Массачусетский Институт Технологий. С. 54–57.
16. Линн Эллиот Кэннон, Сотовый компьютер для реализации алгоритма фильтра Калмана, Технический отчет, к.т.н. Диссертация, Государственный университет Монтаны, 14 июля 1969 г.
17. Hong, J. W .; Кунг, Х. Т. (1981). «Сложность ввода-вывода: игра с красно-синей галькой» (PDF). STOC '81: Материалы тринадцатого ежегодного симпозиума ACM по теории вычислений: 326–333.
18. Ирония, Дрор; Толедо, Сиван; Тискин, Александр (сентябрь 2004 г.). «Нижние границы связи для умножения матриц с распределенной памятью». J. Parallel Distrib. Вычислить. 64 (9): 1017–1026. CiteSeerX  10.1.1.20.7034. Дои:10.1016 / j.jpdc.2004.03.021.
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.

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

• Буттари, Альфредо; Лангу, Жюльен; Курзак, Якуб; Донгарра, Джек (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