Вычислительная сложность умножения матриц

Algorithmic runtime requirements for matrix multiplication

Нерешенная задача в информатике :

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

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

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

Непосредственное применение математического определения умножения матриц дает алгоритм, который требует n ³ полевых операций для умножения двух матриц размера n × n по этому полю ( Θ( n ³ ) в обозначении большого O ). Удивительно, но существуют алгоритмы, которые обеспечивают лучшее время работы, чем этот простой «алгоритм из школьного учебника». Первым был открыт алгоритм Штрассена , разработанный Фолькером Штрассеном в 1969 году и часто называемый «быстрым умножением матриц». ^[1] Оптимальное количество полевых операций, необходимое для умножения двух квадратных матриц размера n × n до постоянных коэффициентов, до сих пор неизвестно. Это главный открытый вопрос в теоретической информатике .

По состоянию на январь 2024 года ^[update]лучшая оценка асимптотической сложности алгоритма умножения матриц равна O( n ^2,371552 ) . ^{[2] [3]} Однако это и подобные улучшения Штрассена на практике не используются, поскольку они представляют собой галактические алгоритмы : постоянный коэффициент, скрытый за большой буквой O, настолько велик, что их целесообразно использовать только для матриц, которые слишком велики для работать на современных компьютерах. ^{[4] [5]}

Простые алгоритмы

Если A , B являются матрицами размера n × n над полем, то их произведение AB также является матрицей размера n × n над этим полем, определяемым поэлементно как

${\displaystyle (AB)_{ij}=\sum _{k=1}^{n}A_{ik}B_{kj}.}$

Алгоритм учебника

Самый простой подход к вычислению произведения двух матриц A и B размера n × n — это вычисление арифметических выражений, вытекающих из определения умножения матриц. В псевдокоде:

на входе  A и B обе матрицы размера n на n инициализируют  C как матрицу размера n на n всех нулей для  i от 1 до n : для  j от 1 до n : для  k от 1 до n : C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ]* B [ k ][ j ] выход  C (как A*B)

В худшем случае этот алгоритм требует ⁠ ⁠ умножения скаляров и ⁠ ⁠ сложения для вычисления произведения двух квадратных матриц размера n × n . Таким образом, его вычислительная сложность равна ⁠ ⁠ в модели вычислений , где полевые операции (сложение и умножение) занимают постоянное время (на практике это относится к числам с плавающей запятой , но не обязательно к целым числам). ${\displaystyle n^{3}}$ ${\displaystyle n^{3}-n^{2}}$ ${\displaystyle O(n^{3})}$

Алгоритм Штрассена

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

В отличие от алгоритмов с более быстрой асимптотической сложностью, на практике используется алгоритм Штрассена. Численная стабильность снижается по сравнению с наивным алгоритмом ^[6] , но он работает быстрее в случаях, когда n > 100 или около того ^[7] и появляется в нескольких библиотеках, таких как BLAS . ^[8] Алгоритмы быстрого умножения матриц не могут обеспечить покомпонентную стабильность , но можно показать, что некоторые из них демонстрируют стабильность по нормам . ^[9] Это очень полезно для больших матриц в точных областях, таких как конечные поля , где численная стабильность не является проблемой.

Показатель умножения матрицы

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

Крупный план 1990–2023 гг.

Показатель умножения матриц , обычно обозначаемый ω , представляет собой наименьшее действительное число, для которого любые две матрицы над полем можно перемножить вместе с помощью операций с полем. Это обозначение обычно используется в исследованиях алгоритмов , так что алгоритмы, использующие умножение матриц в качестве подпрограммы, имеют границы времени выполнения, которые могут обновляться по мере улучшения границ ω . ${\displaystyle n\times n}$ ${\displaystyle n^{\omega +o(1)}}$

Используя наивную нижнюю оценку и умножение школьной матрицы для получения верхней границы, можно прямо заключить, что 2 ≤ ω ≤ 3 . Является ли ω = 2 основным открытым вопросом в теоретической информатике , и существует направление исследований, разрабатывающих алгоритмы умножения матриц для получения улучшенных оценок ω .

Все последние алгоритмы в этом направлении исследований используют лазерный метод , обобщение алгоритма Копперсмита-Винограда, который был предложен Доном Копперсмитом и Шмуэлем Виноградом в 1990 году и был лучшим алгоритмом умножения матриц до 2010 года. ^[24] Концептуальная идея Эти алгоритмы аналогичны алгоритму Штрассена: разработан способ умножения двух k × k -матриц с числом умножений менее k ³ , и этот метод применяется рекурсивно. Лазерный метод имеет ограничения по своей мощности. Амбайнис , Филмус и Ле Галл доказывают, что его нельзя использовать, чтобы показать, что ω < 2,3725, путем анализа все более и более высоких тензорных степеней определенного тождества Копперсмита и Винограда, и ни ω < 2,3078 для широкого диапазона. класс вариантов этого подхода. ^[25] В 2022 году Дуань, Ву и Чжоу разработали вариант, преодолевающий первый из двух барьеров с ω < 2,37188 , ^[23] они сделали это, определив источник потенциальной оптимизации в лазерном методе, называемый комбинированной потерей , который они компенсируют с помощью асимметричная версия метода хеширования в алгоритме Копперсмита – Винограда.

Переформулировка алгоритмов матричного умножения в теории групп

Генри Кон , Роберт Кляйнберг , Балаж Сегеди и Крис Уманс поместили такие методы, как алгоритмы Штрассена и Копперсмита-Винограда, в совершенно другой теоретико-групповой контекст, используя тройки подмножеств конечных групп, которые удовлетворяют свойству непересекаемости, называемому свойством тройного произведения ( ТЭЦ) . Они также выдвигают гипотезы, которые, если они верны, подразумевают существование алгоритмов умножения матриц с по существу квадратичной сложностью. Это означает, что оптимальный показатель умножения матриц равен 2, что, по мнению большинства исследователей, действительно так. ^[5] Одна из таких гипотез заключается в том, что семейства сплетений абелевых групп с симметричными группами реализуют семейства троек подмножества с одновременной версией TPP. ^{[26] [27]} Некоторые из их гипотез с тех пор были опровергнуты Блазиаком, Коном, Чёрчем, Гроховым, Наслундом, Савиным и Умансом с использованием метода ранжирования срезов. ^[28] Кроме того, Алон, Шпилька и Крис Уманс недавно показали, что некоторые из этих гипотез, подразумевающих быстрое умножение матриц, несовместимы с другой правдоподобной гипотезой, гипотезой подсолнуха , ^[29] которая, в свою очередь, связана с проблемой максимального набора. ^[28]

Нижние оценки для ω

Существует тривиальная нижняя оценка ⁠ ⁠ ${\displaystyle \omega \geq 2}$ . Поскольку любой алгоритм умножения двух n × n -матриц должен обрабатывать все 2 n ² элементов, существует тривиальная асимптотическая нижняя граница операций Ω( n ² ) для любого алгоритма матричного умножения. Таким образом ⁠ ⁠ ${\displaystyle 2\leq \omega <2.37188}$ . Неизвестно, есть ли ⁠ ⁠ ${\displaystyle \omega >2}$ . Самая известная нижняя оценка сложности умножения матриц — это Ω( n ² log( n )) для арифметических схем с ограниченными коэффициентами над действительными или комплексными числами, и она принадлежит Рану Разу . ^[30]

Показатель степени ω определяется как предельная точка , поскольку он является нижней границей показателя степени по всем алгоритмам умножения матриц. Известно, что эта предельная точка не достигается. Другими словами, в обычно изучаемой модели вычислений не существует алгоритма умножения матриц, который бы использовал ровно O( n ^ω ) операций; должен быть дополнительный коэффициент n ^o(1) . ^[14]

Умножение прямоугольной матрицы

Подобные методы также применимы к умножению прямоугольных матриц. Центральным объектом исследования является , который является наименьшим из таких, что можно умножить матрицу размера на матрицу размера с помощью арифметических операций. Результат алгебраической сложности гласит, что умножение матриц размера и требует того же количества арифметических операций, что и умножение матриц размера и и размера и , поэтому это включает в себя сложность умножения прямоугольных матриц. ^[31] Это обобщает показатель умножения квадратной матрицы, поскольку . ${\displaystyle \omega (k)}$ ${\displaystyle c}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle \lceil n^{k}\rceil \times n}$ ${\displaystyle O(n^{c+o(1)})}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle \lceil n^{k}\rceil \times n}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$ ${\displaystyle n\times \lceil n^{k}\rceil }$ ${\displaystyle \omega (1)=\omega }$

Поскольку результатом задачи умножения матриц является размер , мы имеем для всех значений . Если можно доказать, что для некоторых значений от 0 до 1 это , то такой результат показывает, что для тех . Наибольшее значение k , известное как показатель умножения двойственной матрицы , обычно обозначается α . α называется « двойственным », поскольку показать это эквивалентно показу того . Как и показатель умножения матрицы, показатель двойного матричного умножения иногда возникает в сложности алгоритмов числовой линейной алгебры и оптимизации. ^[32] ${\displaystyle n^{2}}$ ${\displaystyle \omega (k)\geq 2}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \omega (k)\leq 2}$ ${\displaystyle \omega (k)=2}$ ${\displaystyle k}$ ${\displaystyle \omega (k)=2}$ ${\displaystyle \alpha =1}$ ${\displaystyle \omega =2}$

Первое определение α было сделано Копперсмитом в 1982 году, который показал, что . ^[33] На данный момент лучшая рецензируемая оценка α равна , предложенная Уильямсом, Сюй, Сюй и Чжоу. ^[2] ${\displaystyle \alpha >0.17227}$ ${\displaystyle \alpha \geq 0.321334}$

Связанные проблемы

Задачи, которые имеют ту же асимптотическую сложность, что и умножение матриц, включают определитель , обращение матрицы , исключение Гаусса (см. следующий раздел). Проблемы со сложностью, выражаемой через, включают характеристический полином, собственные значения (но не собственные векторы), нормальную форму Эрмита и нормальную форму Смита . ^{[ нужна цитата ]} ${\displaystyle \omega }$

Обращение матрицы, определитель и исключение Гаусса

В своей статье 1969 года, где он доказал сложность вычисления матриц, Штрассен также доказал, что обращение матрицы , определитель и исключение Гаусса имеют, с точностью до мультипликативной константы, ту же вычислительную сложность , что и умножение матриц. В доказательстве не делается никаких предположений относительно используемого умножения матриц, за исключением того, что его сложность для некоторых ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ ${\displaystyle O(n^{\omega })}$ ${\displaystyle \omega \geq 2}$

Отправной точкой доказательства Штрассена является использование блочного умножения матриц . В частности, матрица четной размерности 2 n × 2 n может быть разделена на четыре блока n × n .

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$

В этой форме его обратным является

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},}$

при условии, что A и обратимы. ${\displaystyle {D}-{CA}^{-1}{B}}$

Таким образом, обратная матрица размером 2 n × 2 n может быть вычислена с помощью двух инверсий, шести умножений и четырех сложений или аддитивных обратных матриц размера n × n . Отсюда следует, что, обозначая соответственно I ( n ) , M ( n ) и A ( n ) = n ² количество операций, необходимых для обращения, умножения и сложения матриц размера n × n , имеем

${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$

Если можно применить эту формулу рекурсивно: ${\displaystyle n=2^{k},}$

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}}$

Если и в конечном итоге получим ${\displaystyle M(n)\leq cn^{\omega },}$ ${\displaystyle \alpha =2^{\omega }\geq 4,}$

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\\&\leq d(2^{k})^{\omega }\end{aligned}}}$

для некоторой постоянной d .

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

Это доказывает заявленную сложность матриц, в которых все подматрицы, которые необходимо инвертировать, действительно обратимы. Таким образом, эта сложность доказана почти для всех матриц, поскольку матрица со случайно выбранными элементами обратима с вероятностью единица.

Тот же аргумент применим и к LU-разложению , так как, если матрица A обратима, равенство

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}}$

определяет блочное LU-разложение, которое может применяться рекурсивно для получения в конечном итоге истинного LU-разложения исходной матрицы. ${\displaystyle A}$ ${\displaystyle D-CA^{-1}B,}$

Этот аргумент применим также и к определителю, поскольку он является результатом блочного LU-разложения, которое

${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$

Минимизация количества умножений

С проблемой минимизации количества арифметических операций связана минимизация количества умножений, что обычно является более дорогостоящей операцией, чем сложение. Алгоритм умножения матриц обязательно должен использовать только операции умножения, но эти алгоритмы непрактичны. В отличие от простых умножений из школьных учебников, матрицы в можно выполнить за 47 умножений, ^[34] умножение матриц над коммутативным кольцом можно выполнить за 21 умножение ^{[35] [36]} (23, если некоммутативно ^[37] ). Нижняя граница необходимых умножений равна 2 mn +2 n − m −2 (умножение n × m -матриц на m × n -матрицы методом подстановки, m ⩾ n ⩾3), что означает, что для случая n=3 требуется минимум 19 умножений и n=4 не менее 34. ^[38] Для n=2 оптимальных 7 умножений 15 сложений являются минимальными по сравнению с только 4 сложениями для 8 умножений. ^{[39] [40]} ${\displaystyle O(n^{\omega })}$ ${\displaystyle O(n^{\omega })}$ ${\displaystyle n^{3}}$ ${\displaystyle 4\times 4}$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle 3\times 3}$

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

• Вычислительная сложность математических операций
• Алгоритм CYK, алгоритм §Валианта
• Алгоритм Фрейвалдса , простой алгоритм Монте-Карло ^, который, учитывая матрицы A , B и C , проверяет за время Θ( n2 ) , если AB = C.
• Умножение цепочки матриц
• Умножение матриц для абстрактных определений
• Алгоритм умножения матриц , подробности практической реализации
• Умножение разреженной матрицы на вектор

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

1. Фолькер Штрассен (август 1969 г.). «Исключение по Гауссу не является оптимальным». Нумерическая математика . 13 (4): 354–356. дои : 10.1007/BF02165411. S2CID  121656251.
2. Василевска Уильямс, Вирджиния; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Ренфэй. Новые границы умножения матриц: от альфы до омеги . Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2024 года. стр. 3792–3835. arXiv : 2307.07970 . дои : 10.1137/1.9781611977912.134.
3. Надис, Стив (7 марта 2024 г.). «Новый прорыв приближает умножение матриц к идеалу» . Проверено 9 марта 2024 г.
4. Илиопулос, Костас С. (1989). «Оценки сложности в наихудшем случае алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы» (PDF) . SIAM Journal по вычислительной технике . 18 (4): 658–669. CiteSeerX 10.1.1.531.9309 . дои : 10.1137/0218045. MR  1004789. Архивировано из оригинала (PDF) 5 марта 2014 г. Проверено 16 января 2015 г. Алгоритм Копперсмита-Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений. 
5. Робинсон, Сара (ноябрь 2005 г.). «К оптимальному алгоритму умножения матриц» (PDF) . СИАМ Новости . 38 (9). Даже если кому-то удастся доказать одну из гипотез, показав тем самым, что ω = 2 , подход сплетения вряд ли будет применим к большим матричным задачам, возникающим на практике. [...] входные матрицы должны быть астрономически большими, чтобы разница во времени была очевидна.
6. Миллер, Уэбб (1975). «Вычислительная сложность и численная устойчивость». СИАМ Новости . 4 (2): 97–107. CiteSeerX 10.1.1.148.9947 . дои : 10.1137/0204009. 
7. Скиена, Стивен (2012). «Сортировка и поиск». Руководство по проектированию алгоритмов . Спрингер. стр. 45–46, 401–403. дои : 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
8. Пресс, Уильям Х.; Фланнери, Брайан П.; Теукольский, Саул А. ; Веттерлинг, Уильям Т. (2007). Численные рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета . п. 108. ИСБН 978-0-521-88068-8.
9. Баллард, Грей; Бенсон, Остин Р.; Друинский, Алекс; Липшиц, Бенджамин; Шварц, Одед (2016). «Повышение численной стабильности быстрого умножения матриц». Журнал SIAM по матричному анализу и приложениям . 37 (4): 1382–1418. arXiv : 1507.00687 . дои : 10.1137/15M1032168. S2CID  2853388.
10. Виктор Яковлевич Пан (октябрь 1978 г.). «Алгоритм Штрассена не оптимален: трилинейный метод агрегирования, объединения и отмены для построения быстрых алгоритмов для матричных операций». Учеб. 19-й ФОКС . стр. 166–176. дои : 10.1109/SFCS.1978.34. S2CID  14348408.
11. Дарио Андреа Бини; Мильвио Каповани; Франческо Романи; Грация Лотти (июнь 1979 г.). " O ( п 2.7799 ) {\displaystyle O(n^{2.7799})} сложность приблизительного умножения матриц n × n {\displaystyle n\times n}". Письма об обработке информации . 8 (5): 234–235. дои : 10.1016/0020-0190(79)90113-3.
12. А. Шенхаге (1981). «Частичное и полное умножение матриц». SIAM Journal по вычислительной технике . 10 (3): 434–455. дои : 10.1137/0210032.
13. Франческо Романи (1982). «Некоторые свойства непересекающихся сумм тензоров, связанные с умножением матриц». SIAM Journal по вычислительной технике . 11 (2): 263–267. дои : 10.1137/0211020.
14. Д. Копперсмит; С. Виноград (1981). «Об асимптотической сложности умножения матриц». Учеб. 22-й ежегодный симпозиум по основам информатики (FOCS) . стр. 82–90. дои : 10.1109/SFCS.1981.27. S2CID  206558664.
15. Фолькер Штрассен (октябрь 1986 г.). «Асимптотический спектр тензоров и показатель степени матричного умножения». Учеб. 27-я Энн. Симп. о Фонде компьютерных наук (FOCS) . стр. 49–54. дои : 10.1109/SFCS.1986.52. ISBN 0-8186-0740-8. S2CID  15077423.
16. Д. Копперсмит; С. Виноград (март 1990 г.). «Умножение матриц с помощью арифметических прогрессий». Журнал символических вычислений . 9 (3): 251–280. дои : 10.1016/S0747-7171(08)80013-2 .
17. Стотерс, Эндрю Джеймс (2010). О сложности умножения матриц (кандидатская диссертация). Эдинбургский университет.
18. Вирджиния Василевска Уильямс (2012). «Умножение матриц быстрее, чем Копперсмит-Виноград». У Говарда Дж. Карлоффа; Тонианн Питасси (ред.). Учеб. 44-й симпозиум по теории вычислений (STOC) . АКМ. стр. 887–898. дои : 10.1145/2213977.2214056. ISBN 978-1-4503-1245-5. S2CID  14350287.
19. Уильямс, Вирджиния Василевска . Умножение матриц за время (PDF) (Технический отчет). Стэндфордский Университет.
20. Ле Галль, Франсуа (2014). «Алгебраическая теория сложности и умножение матриц». В Кацусуке Набэсима (ред.). Материалы 39-го Международного симпозиума по символьным и алгебраическим вычислениям - ISSAC '14 . стр. 296–303. arXiv : 1401.7714 . Бибкод : 2014arXiv1401.7714L. дои : 10.1145/2608628.2627493. ISBN 978-1-4503-2501-1. S2CID  2597483.
21. Алман, Джош; Уильямс, Вирджиния Василевска (2020). «Усовершенствованный лазерный метод и более быстрое умножение матриц». 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021). arXiv : 2010.05846 .
22. Хартнетт, Кевин (23 марта 2021 г.). «Умножение матрицы на несколько дюймов ближе к мифической цели». Журнал Кванта . Проверено 1 апреля 2021 г.
23. Дуан, Ран; У, Хунсюнь; Чжоу, Жэньфэй (2022). «Более быстрое умножение матриц посредством асимметричного хеширования». arXiv : 2210.10173 [cs.DS].
24. Копперсмит, Дон; Виноград, Шмуэль (1990). «Умножение матриц с помощью арифметических прогрессий» (PDF) . Журнал символических вычислений . 9 (3): 251. doi : 10.1016/S0747-7171(08)80013-2 .
25. Амбайнис, Андрис; Фильмус, Юваль; Ле Галль, Франсуа (14 июня 2015 г.). «Быстрое умножение матриц». Материалы сорок седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '15. Портленд, Орегон, США: Ассоциация вычислительной техники. стр. 585–593. arXiv : 1411.5414 . дои : 10.1145/2746539.2746554. ISBN 978-1-4503-3536-2. S2CID  8332797.
26. Кон, Х.; Кляйнберг, Р.; Сегеди, Б.; Уманс, К. (2005). «Теоретико-групповые алгоритмы умножения матриц». 46-й ежегодный симпозиум IEEE по основам информатики (FOCS'05). п. 379. дои :10.1109/SFCS.2005.39. ISBN 0-7695-2468-0. S2CID  41278294.
27. Кон, Генри; Уманс, Крис (2003). «Теоретико-групповой подход к быстрому умножению матриц». Материалы 44-го ежегодного симпозиума IEEE по основам информатики, 11–14 октября 2003 г. Компьютерное общество IEEE. стр. 438–449. arXiv : math.GR/0307321 . дои : 10.1109/SFCS.2003.1238217. ISBN 0-7695-2040-5. S2CID  5890100.
28. Блазиак, Дж.; Кон, Х.; Черч, Т.; Грочоу, Дж.; Наслунд, Э.; Савин, В.; Уманс, К. (2017). «О наборах ограничений и теоретико-групповом подходе к умножению матриц». Дискретный анализ. п. 1245. дои :10.19086/da.1245. S2CID  9687868.
29. Алон, Н .; Шпилька, А.; Уманс, К. (апрель 2011 г.). «О подсолнухах и умножении матриц». Электронный коллоквиум по вычислительной сложности . ТР11-067.
30. Раз, Ран (2002). «О сложности матричного произведения». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . стр. 144–151. дои : 10.1145/509907.509932. ISBN 1581134959. S2CID  9582328.
31. Галль, Франсуа Ле; Уррутия, Флоран (01 января 2018 г.). Улучшено умножение прямоугольных матриц с использованием степеней тензора Копперсмита-Винограда. Слушания. Общество промышленной и прикладной математики. стр. 1029–1046. arXiv : 1708.05622 . дои : 10.1137/1.9781611975031.67. ISBN 978-1-61197-503-1. S2CID  33396059 . Проверено 23 мая 2021 г. {{cite book}}: |work=игнорируется ( помощь )
32. Коэн, Майкл Б.; Ли, Инь Тат; Сун, Чжао (05 января 2021 г.). «Решение линейных программ за время умножения текущей матрицы». Журнал АКМ . 68 (1): 3:1–3:39. arXiv : 1810.07896 . дои : 10.1145/3424305. ISSN  0004-5411. S2CID  231955576.
33. Копперсмит, Д. (1 августа 1982 г.). «Быстрое умножение прямоугольных матриц» . SIAM Journal по вычислительной технике . 11 (3): 467–471. дои : 10.1137/0211037. ISSN  0097-5397.
34. См. Рис. 1 расширенных данных: Алгоритм умножения матриц 4 × 4 в модульной арифметике ( Z 2 {\displaystyle \mathbb {Z} _{2}}) с 47 умножениями в Фавзи, А.; Балог, М.; Хуанг, А.; Хьюберт, Т.; Ромера-Паредес, Б.; Барекатайн, М.; Новиков А.; р Руис, Ф.Дж.; Шритвизер, Дж.; Свирщ, Г.; Сильвер, Д.; Хассабис, Д.; Кохли, П. (2022). «Открытие более быстрых алгоритмов матричного умножения с помощью обучения с подкреплением». Природа . 610 (7930): 47–53. Бибкод : 2022Natur.610...47F. дои : 10.1038/s41586-022-05172-4. ПМЦ 9534758 . ПМИД  36198780. 
35. Розовский, Андреас (27 июля 2020 г.). «Алгоритм быстрой коммутативной матрицы». arXiv : 1904.07683 . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
36. Макаров, О.М. (1986). «Алгоритм умножения матриц 3×3». Журнал Вычислительной Математики и Математической Физики . 26 (2): 293–294 . Проверено 5 октября 2022 г.

    Также у Макарова О.М. (1986). «Алгоритм умножения матриц 3×3». Вычислительная математика и математическая физика СССР . 26 : 179–180. дои : 10.1016/0041-5553(86)90203-X.

37. Ладерман, Джулиан Д. (1976). «Некоммутативный алгоритм умножения матриц 3 × 3 с использованием 23 умножений». Бюллетень Американского математического общества . 82 (1): 126–128. дои : 10.1090/S0002-9904-1976-13988-2 . ISSN  0002-9904.
38. Блазер, Маркус (февраль 2003 г.). «О сложности умножения матриц малых форматов». Журнал сложности . 19 (1): 43–60. дои : 10.1016/S0885-064X(02)00007-9 .
39. Виноград, С. (1 октября 1971). «Об умножении матриц 2×2». Линейная алгебра и ее приложения . 4 (4): 381–388. дои : 10.1016/0024-3795(71)90009-7 . ISSN  0024-3795.
40. Л., Проберт, Р. (1973). О сложности умножения матриц. Университет Ватерлоо. ОСЛК  1124200063.{{cite book}}: CS1 maint: multiple names: authors list (link)

Внешние ссылки

• Еще один каталог быстрых алгоритмов умножения матриц
• Фавзи, А.; Балог, М.; Хуанг, А.; Хьюберт, Т.; Ромера-Паредес, Б.; Барекатайн, М.; Новиков А.; Руис, ФЕДР; Шритвизер, Дж.; Свирщ, Г.; Сильвер, Д.; Хассабис, Д.; Кохли, П. (2022). «Открытие более быстрых алгоритмов матричного умножения с помощью обучения с подкреплением». Природа . 610 (7930): 47–53. Бибкод : 2022Natur.610...47F. дои : 10.1038/s41586-022-05172-4. ПМЦ  9534758 . ПМИД  36198780.