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

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

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

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

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

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

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

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

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

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

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

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

input A and B, both n by n matrices
initialize C to be an n by n matrix of all zeros
for i from 1 to n:
    for j from 1 to n:
        for k from 1 to n:
            C[i][j] = C[i][j] + A[i][k]*B[k][j]
output C (as A*B)

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

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

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

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

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

Хронология показателя умножения матрицы
Год	Связанный с омегой	Авторы
1969	2.8074	улицы ^[1]
1978	2.796	Кастрюля ^[10]
1979	2.780	Бини, Каповани [ ит ] , римляне ^[11]
1981	2.522	Шенхаге ^[12]
1981	2.517	РИМЛЯНАМ ^[13]
1981	2.496	Медник , Виноград ^[14]
1986	2.479	улицы ^[15]
1990	2.3755	Медник , Виноград ^[16]
2010	2.3737	Стотерс ^[17]
2012	2.3729	Уильямс ^[18]^[19]
2014	2.3728639	Ле Галль ^[20]
2020	2.3728596	Алман, Уильямс ^[21]^[22]
2022	2.371866	Дуань, Ву, Чжоу ^[23]
2024	2.371552	Уильямс , Сюй, Сюй и Чжоу ^[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I(2n)\leq 2I(n)+6M(n)+4A(n).

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

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

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

{\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$ обратима, равенство

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

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

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

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

С проблемой минимизации количества арифметических операций связана минимизация количества умножений, что обычно является более дорогостоящей операцией, чем сложение. А $O(n^{\omega })$ алгоритм умножения матриц должен обязательно использовать только $O(n^{\omega })$ операции умножения, но эти алгоритмы непрактичны. Улучшение от наивного $n^{3}$ умножение для школьного умножения, $4\times 4$ матрицы в $\mathbb {Z} /2\mathbb {Z}$ можно сделать с помощью 47 умножений, ^[34] $3\times 3$ умножение матриц над коммутативным кольцом можно выполнить за 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]

См. также

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

Ссылки

^ Jump up to: ^а ^б Фолькер Штрассен (август 1969 г.). «Исключение по Гауссу не является оптимальным» . Численная математика . 13 (4): 354–356. дои : 10.1007/BF02165411 . S2CID 121656251 .
^ Jump up to: ^а ^б ^с Василевска Уильямс, Вирджиния; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Ренфэй. Новые границы умножения матриц: от альфы до омеги . Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2024 года. стр. 3792–3835. arXiv : 2307.07970 . дои : 10.1137/1.9781611977912.134 .
^ Надис, Стив (7 марта 2024 г.). «Новый прорыв приближает умножение матриц к идеалу» . Проверено 9 марта 2024 г.
^ Илиопулос, Костас С. (1989). «Оценки сложности в наихудшем случае алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы» (PDF) . SIAM Journal по вычислительной технике . 18 (4): 658–669. CiteSeerX 10.1.1.531.9309 . дои : 10.1137/0218045 . МР 1004789 . Архивировано из оригинала (PDF) 5 марта 2014 г. Проверено 16 января 2015 г. Алгоритм Копперсмита-Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений.
^ Jump up to: ^а ^б Робинсон, Сара (ноябрь 2005 г.). «К оптимальному алгоритму умножения матриц» (PDF) . СИАМ Новости . 38 (9). Даже если кому-то удастся доказать одну из гипотез, показав тем самым, что $ω = 2$ , подход сплетения вряд ли будет применим к большим матричным задачам, возникающим на практике. [...] входные матрицы должны быть астрономически большими, чтобы разница во времени была очевидна.
^ Миллер, Уэбб (1975). «Вычислительная сложность и численная устойчивость». СИАМ Новости . 4 (2): 97–107. CiteSeerX 10.1.1.148.9947 . дои : 10.1137/0204009 .
^ Скиена, Стивен (2012). «Сортировка и поиск». Руководство по проектированию алгоритмов . Спрингер. стр. 45–46 , 401–403. дои : 10.1007/978-1-84800-070-4_4 . ISBN 978-1-84800-069-8 .
^ Пресс, Уильям Х.; Фланнери, Брайан П.; Теукольский, Саул А. ; Веттерлинг, Уильям Т. (2007). Численные рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета . п. 108 . ISBN 978-0-521-88068-8 .
^ Баллард, Грей; Бенсон, Остин Р.; Друинский, Алекс; Липшиц, Бенджамин; Шварц, Одед (2016). «Повышение численной стабильности быстрого умножения матриц». Журнал SIAM по матричному анализу и приложениям . 37 (4): 1382–1418. arXiv : 1507.00687 . дои : 10.1137/15M1032168 . S2CID 2853388 .
^ Виктор Яковлевич Пан (октябрь 1978 г.). «Алгоритм Штрассена не оптимален: трилинейный метод агрегирования, объединения и отмены для построения быстрых алгоритмов для матричных операций». Учеб. 19-й ФОКС . стр. 166–176. дои : 10.1109/SFCS.1978.34 . S2CID 14348408 .
^ Дарио Андреа Бини; Мильвио Каповани; Франческо Романи; Грация Лотти (июнь 1979 г.). " $O(n^{2.7799})$ сложность для $n\times n$ приблизительное матричное умножение» . Information Processing Letters . 8 (5): 234–235. doi : 10.1016/0020-0190(79)90113-3 .
^ А. Шенхаге (1981). «Частичное и полное умножение матриц». SIAM Journal по вычислительной технике . 10 (3): 434–455. дои : 10.1137/0210032 .
^ Франческо Романи (1982). «Некоторые свойства непересекающихся сумм тензоров, связанные с умножением матриц». SIAM Journal по вычислительной технике . 11 (2): 263–267. дои : 10.1137/0211020 .
^ Jump up to: ^а ^б Д. Копперсмит; С. Виноград (1981). «Об асимптотической сложности умножения матриц». Учеб. 22-й ежегодный симпозиум по основам информатики (FOCS) . стр. 82–90. дои : 10.1109/SFCS.1981.27 . S2CID 206558664 .
^ Фолькер Штрассен (октябрь 1986 г.). «Асимптотический спектр тензоров и показатель степени матричного умножения». Учеб. 27-я Энн. Симп. о Фонде компьютерных наук (FOCS) . стр. 49–54. дои : 10.1109/SFCS.1986.52 . ISBN 0-8186-0740-8 . S2CID 15077423 .
^ Д. Копперсмит; С. Виноград (март 1990 г.). «Умножение матриц с помощью арифметических прогрессий» . Журнал символических вычислений . 9 (3): 251–280. дои : 10.1016/S0747-7171(08)80013-2 .
^ Стотерс, Эндрю Джеймс (2010). О сложности умножения матриц (кандидатская диссертация). Эдинбургский университет.
^ Вирджиния Василевска Уильямс (2012). «Умножение матриц быстрее, чем Копперсмит-Виноград». У Говарда Дж. Карлоффа; Тонианн Питасси (ред.). Учеб. 44-й симпозиум по теории вычислений (STOC) . АКМ. стр. 887–898. дои : 10.1145/2213977.2214056 . ISBN 978-1-4503-1245-5 . S2CID 14350287 .
^ Уильямс, Вирджиния Василевска . Умножение матриц в $O(n^{2.373})$ время (PDF) (Технический отчет). Стэнфордский университет.
^ Ле Галль, Франсуа (2014). «Алгебраическая теория сложности и умножение матриц». В Кацусуке Набэсима (ред.). Материалы 39-го Международного симпозиума по символьным и алгебраическим вычислениям - ISSAC '14 . стр. 296–303. arXiv : 1401.7714 . Бибкод : 2014arXiv1401.7714L . дои : 10.1145/2608628.2627493 . ISBN 978-1-4503-2501-1 . S2CID 2597483 .
^ Алман, Джош; Уильямс, Вирджиния Василевска (2020). «Усовершенствованный лазерный метод и более быстрое умножение матриц». 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021) . arXiv : 2010.05846 .
^ Хартнетт, Кевин (23 марта 2021 г.). «Умножение матриц на несколько дюймов ближе к мифической цели» . Журнал Кванта . Проверено 1 апреля 2021 г.
^ Jump up to: ^а ^б Дуан, Ран; У, Хунсюнь; Чжоу, Жэньфэй (2022). «Более быстрое умножение матриц посредством асимметричного хеширования». arXiv : 2210.10173 [ cs.DS ].
^ Копперсмит, Дон; Виноград, Шмуэль (1990). «Умножение матриц с помощью арифметических прогрессий» (PDF) . Журнал символических вычислений . 9 (3): 251. doi : 10.1016/S0747-7171(08)80013-2 .
^ Амбайнис, Андрис; Фильмус, Юваль; Ле Галль, Франсуа (14 июня 2015 г.). «Быстрое умножение матриц» . Материалы сорок седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '15. Портленд, Орегон, США: Ассоциация вычислительной техники. стр. 585–593. arXiv : 1411.5414 . дои : 10.1145/2746539.2746554 . ISBN 978-1-4503-3536-2 . S2CID 8332797 .
^ Кон, Х.; Кляйнберг, Р.; Сегеди, Б.; Уманс, К. (2005). «Теоретико-групповые алгоритмы умножения матриц». 46-й ежегодный симпозиум IEEE по основам информатики (FOCS'05) . п. 379. дои : 10.1109/SFCS.2005.39 . ISBN 0-7695-2468-0 . S2CID 41278294 .
^ Кон, Генри; Уманс, Крис (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 .
^ Jump up to: ^а ^б Блазиак, Дж.; Кон, Х.; Черч, Т.; Грочоу, Дж.; Наслунд, Э.; Савин, В.; Уманс, К. (2017). «О наборах ограничений и теоретико-групповом подходе к умножению матриц». Дискретный анализ . п. 1245. дои : 10.19086/da.1245 . S2CID 9687868 .
^ Алон, Н. ; Шпилька, А.; Уманс, К. (апрель 2011 г.). «О подсолнухах и умножении матриц» . Электронный коллоквиум по вычислительной сложности . ТР11-067.
^ Раз, Ран (2002). «О сложности матричного произведения». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . стр. 144–151. дои : 10.1145/509907.509932 . ISBN 1581134959 . S2CID 9582328 .
^ Галль, Франсуа Ле; Уррутия, Флоран (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= игнорируется ( помогите )
^ Коэн, Майкл Б.; Ли, Инь Тат; Сун, Чжао (05 января 2021 г.). «Решение линейных программ за время умножения текущей матрицы» . Журнал АКМ . 68 (1): 3:1–3:39. arXiv : 1810.07896 . дои : 10.1145/3424305 . ISSN 0004-5411 . S2CID 231955576 .
^ Копперсмит, Д. (1 августа 1982 г.). «Быстрое умножение прямоугольных матриц» . SIAM Journal по вычислительной технике . 11 (3): 467–471. дои : 10.1137/0211037 . ISSN 0097-5397 .
^ См . Рисунок 1 расширенных данных: Алгоритм умножения матриц 4 × 4 в модульной арифметике ( $\mathbb {Z} _{2}$ )) с 47 умножениями в Фавзи, А.; Балог, М.; Хуанг, А.; Хьюберт, Т.; Ромера-Паредес, Б.; Барекатайн, М.; Новиков А.; р Руис, Ф.Дж.; Шритвизер, Дж.; Свирщ, Г.; Сильвер, Д.; Хассабис, Д.; Кохли, П. (2022). «Открытие более быстрых алгоритмов матричного умножения с помощью обучения с подкреплением» . Природа . 610 (7930): 47–53. Бибкод : 2022Natur.610...47F . дои : 10.1038/s41586-022-05172-4 . ПМЦ 9534758 . ПМИД 36198780 .
^ Розовский, Андреас (27 июля 2020 г.). «Алгоритм быстрой коммутативной матрицы». arXiv : 1904.07683 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Makarov, O. M. (1986). "An algorithm for multiplying 3×3 matrices" . Zhurnal Vychislitel'noi Matematiki I Matematicheskoi Fiziki . 26 (2): 293–294 . Retrieved 5 October 2022 .
Также в Макаров О.М. (1986). «Алгоритм умножения матриц 3×3». Вычислительная математика и математическая физика СССР . 26 : 179–180. дои : 10.1016/0041-5553(86)90203-X .
^ Ладерман, Джулиан Д. (1976). «Некоммутативный алгоритм умножения матриц 3×3 с использованием 23 умножений» . Бюллетень Американского математического общества . 82 (1): 126–128. дои : 10.1090/S0002-9904-1976-13988-2 . ISSN 0002-9904 .
^ Блазер, Маркус (февраль 2003 г.). «О сложности умножения матриц малых форматов» . Журнал сложности . 19 (1): 43–60. дои : 10.1016/S0885-064X(02)00007-9 .
^ Виноград, С. (1 октября 1971 г.). «Об умножении матриц 2×2» . Линейная алгебра и ее приложения . 4 (4): 381–388. дои : 10.1016/0024-3795(71)90009-7 . ISSN 0024-3795 .
^ Л., Проберт Р. (1973). О сложности умножения матриц . Университет Ватерлоо. OCLC 1124200063 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

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

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

[strassen69-1] Jump up to: ^а ^б Фолькер Штрассен (август 1969 г.). «Исключение по Гауссу не является оптимальным» . Численная математика . 13 (4): 354–356. дои : 10.1007/BF02165411 . S2CID 121656251 .

[wxxz23-2] Jump up to: ^а ^б ^с Василевска Уильямс, Вирджиния; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Ренфэй. Новые границы умножения матриц: от альфы до омеги . Материалы ежегодного симпозиума 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 . МР 1004789 . Архивировано из оригинала (PDF) 5 марта 2014 г. Проверено 16 января 2015 г. Алгоритм Копперсмита-Винограда непрактичен из-за очень большой скрытой константы в верхней границе количества требуемых умножений.

[robinson-5] Jump up to: ^а ^б Робинсон, Сара (ноябрь 2005 г.). «К оптимальному алгоритму умножения матриц» (PDF) . СИАМ Новости . 38 (9). Даже если кому-то удастся доказать одну из гипотез, показав тем самым, что $ω = 2$ , подход сплетения вряд ли будет применим к большим матричным задачам, возникающим на практике. [...] входные матрицы должны быть астрономически большими, чтобы разница во времени была очевидна.

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

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

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

[bdl16-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(n^{2.7799})$ сложность для $n\times n$ приблизительное матричное умножение» . Information Processing Letters . 8 (5): 234–235. doi : 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 .

[CW.81-14] Jump up to: ^а ^б Д. Копперсмит; С. Виноград (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 .

[Williams.2014-19] Уильямс, Вирджиния Василевска . Умножение матриц в $O(n^{2.373})$ время (PDF) (Технический отчет). Стэнфордский университет.

[LeGall2014-20] Ле Галль, Франсуа (2014). «Алгебраическая теория сложности и умножение матриц». В Кацусуке Набэсима (ред.). Материалы 39-го Международного симпозиума по символьным и алгебраическим вычислениям - ISSAC '14 . стр. 296–303. arXiv : 1401.7714 . Бибкод : 2014arXiv1401.7714L . дои : 10.1145/2608628.2627493 . ISBN 978-1-4503-2501-1 . S2CID 2597483 .

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

[22] Хартнетт, Кевин (23 марта 2021 г.). «Умножение матриц на несколько дюймов ближе к мифической цели» . Журнал Кванта . Проверено 1 апреля 2021 г.

[dwz22-23] Jump up to: ^а ^б Дуан, Ран; У, Хунсюнь; Чжоу, Жэньфэй (2022). «Более быстрое умножение матриц посредством асимметричного хеширования». arXiv : 2210.10173 [ cs.DS ].

[coppersmith-24] Копперсмит, Дон; Виноград, Шмуэль (1990). «Умножение матриц с помощью арифметических прогрессий» (PDF) . Журнал символических вычислений . 9 (3): 251. doi : 10.1016/S0747-7171(08)80013-2 .

[afl142-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 .

[:0-28] Jump up to: ^а ^б Блазиак, Дж.; Кон, Х.; Черч, Т.; Грочоу, Дж.; Наслунд, Э.; Савин, В.; Уманс, К. (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 .

[gall18-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 в модульной арифметике ( $\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] Makarov, O. M. (1986). "An algorithm for multiplying 3×3 matrices" . Zhurnal Vychislitel'noi Matematiki I Matematicheskoi Fiziki . 26 (2): 293–294 . Retrieved 5 October 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). О сложности умножения матриц . Университет Ватерлоо. OCLC 1124200063 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[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]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]