행렬 곱셈의 계산 복잡도

이론 컴퓨터 과학에서 행렬 곱셈의 계산 복잡도는 행렬 곱셈의 연산을 얼마나 빨리 수행할 수 있는지를 지시합니다.행렬 곱셈 알고리즘은 수치 선형 대수와 최적화를 위한 이론적 및 수치적 알고리즘의 중심 서브루틴이므로, 적절한 시간이 걸리는 것을 찾는 것이 실질적으로 중요합니다.

행렬 곱셈의 수학적 정의를 직접 적용하면 n개의 필드 연산이 해당 필드 위에 두 개의 n × n 행렬을 곱해야 하는³ 알고리즘이 제공됩니다(큰 O 표기법의 Ω(n³)).놀랍게도, 이 간단한 "교감 알고리즘"보다 더 나은 실행 시간을 제공하는 알고리즘이 존재합니다.최초로 발견된 것은 1969년 볼커 스트라센이 고안한 스트라센의 알고리즘으로, 종종 "빠른 행렬 곱셈"^[1]이라고 불립니다.두 제곱 n × n 행렬을 상수 인자까지 곱하는 데 필요한 최적의 필드 연산 수는 여전히 알 수 없습니다.이것은 이론 컴퓨터 과학에서 중요한 미해결 문제입니다.

2023년 7월^[update] 현재 행렬 곱셈 알고리즘의 점근적 복잡성에 대해 가장 잘 발표된 경계는 미리 인쇄된 글에서 발표된 윌리엄스, 쉬, 쉬 및 ^[2]저우에 의해 주어진 O(n^2.371552) 시간입니다.이것은 Duan, Wu 및 ^[3]Zhou의 사전 인쇄에 의해 주어진 O(n^2.371866)의 경계를 개선합니다.그러나 이것과 Strassen과 유사한 개선점은 은하 알고리즘이기 때문에 실제로는 사용되지 않습니다. Big O 표기법에 의해 가려지는 상수 계수가 너무 커서 오늘날의 ^[4][5]컴퓨터에서 처리하기에는 너무 큰 행렬에만 가치가 있습니다.피어 리뷰에 의해 확인된 최상의 시간 제한은 O(^[6]n^2.3728596)입니다.

간단한 알고리즘

만약 A, B가 어떤 필드 위에 있는 n × n 행렬이라면, 그들의 곱 AB는 또한 그 필드 위에 있는 n × n 행렬이고, 다음과 같이 엔트리와 같이 정의됩니다.

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

교과서 알고리즘

두 n×n 행렬 A와 B의 곱을 계산하는 가장 간단한 방법은 행렬 곱의 정의에서 나오는 산술 식을 계산하는 것입니다.의사 코드:

입력 A와 B, n의 n 행렬 모두 C를 i의 모든 0의 n의 n 행렬로 초기화합니다. 1부터 n의 j의 경우: 1부터 n의 k: 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 {}^{}}$의 3${\displaystyle {}^{}{-n2개}^{}}$의 ${\$ n$^{3}-$n^{2$}$개의 덧셈이 $필요$합니다.$따라서{\displaystyle }$ 필드 연산( 덧셈 및 곱셈)이 일정한 시간이 걸리는 계산 모델에서 계산 복잡도는 O${\displaystyle ({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}${\$displaystyle$ O$(n^{3$입니다(실제로는 부동 소수점 숫자의 경우이지만 반드시 정수의 경우는 아닙니다).

스트라센 알고리즘

Strassen의 알고리즘은 분할 정복 접근법을 통해 순진한 행렬 곱셈을 개선합니다.핵심적인 관찰은 2×2 행렬의 곱셈이 일반적인 8 곱셈이 아니라 7 곱셈만으로 수행될 수 있다는 것입니다(11번의 추가 덧셈 및 뺄셈 연산의 희생).즉, 입력된 nxn 행렬을 블록 2x2 행렬로 취급하면 nxn 행렬을 곱하는 작업을 n/2xn/2 행렬을 곱하는 7개의 하위 문제로 줄일 수 있습니다.이를 재귀적으로 적용하면 O${\displaystyle }$(${\displaystyle {n_{}}^{}}$ ${\displaystyle {{log\mathrm{}}_{}}^{}}$ 2 ${\displaystyle {{}_{}}^{}{7}^{}}$ ) ${\displaystyle \ge O}$ (${\displaystyle n^{}}$ 2${\displaystyle {.807}^{}}${\$displaystyle$O($n^{\log$ _${2}7})\prox$ O$(n^{2.807})$ 필드$$ 연산이 $필요$한 알고리즘이 제공됩니다.

Strassen의 알고리즘은 점근 복잡도가 빠른 알고리즘과 달리 실제로 사용됩니다.naive ^[7]알고리즘에 비해 수치 안정성이 떨어지지만, n > 100 정도인^[8] 경우와 BLAS와 ^[9]같은 여러 라이브러리에 나타나는 경우가 더 빠릅니다.빠른 행렬 곱셈 알고리즘은 성분 단위의 안정성을 얻을 수 없지만 일부는 표준 단위의 ^[10]안정성을 나타낼 수 있습니다.수치 안정성이 문제가 되지 않는 유한장과 같은 정확한 영역에서 큰 행렬에 매우 유용합니다.

행렬 곱셈 지수

행렬 곱셈 지수의 타임라인

연도	오메가에 바운드	작가들
1969	2.8074	스트라센[1]
1978	2.796	팬[11]
1979	2.780	비니, 카포바니, 로마니[12]
1981	2.522	쇤하게[13]
1981	2.517	로마니[14]
1981	2.496	코퍼스미스, 위노그라드[15]
1986	2.479	스트라센[16]
1990	2.3755	코퍼스미스, 위노그라드[17]
2010	2.3737	스토더스[18]
2013	2.3729	윌리엄스[19][20]
2014	2.3728639	르[21] 갈
2020	2.3728596	앨먼, 윌리엄스[6][22]
2022	2.371866	an, 우, 주
2023	2.371552	윌리엄스, 쉬, 쉬, 저우[2]

일반적으로 ω로 표시되는 행렬 곱셈 지수는 n${\displaystyle {}^{}}$ω +${\displaystyle o^{}}$ (${\displaystyle {1)}^{}}${\$displaystyle$$$n$^{\omega +$ o (1)} 필드 연산을 $사용$하여 필드 위에 두${\displaystyle 개}$의 n$$× n {\displaystyle n^{\$omega$ + o ($1$$)}$개의 행렬을 함께 곱할 수 있는 가장 작은 실수입니다.이 표기법은 알고리즘 연구에서 일반적으로 사용되며, 행렬 곱셈을 서브루틴으로 사용하는 알고리즘은 실행 시간에 대한 경계가 ω에 대한 경계가 향상됨에 따라 업데이트될 수 있습니다.

상한에 대한 순진한 하한과 교과서 행렬 곱셈을 사용하면 2 ≤ ≤ ≤ 3이라고 직접 결론을 내릴 수 있습니다.δ = 2가 이론 컴퓨터 과학의 주요 미해결 문제이며, δ에 대한 개선된 경계를 얻기 위해 행렬 곱셈 알고리즘을 개발하는 연구 라인이 있습니다.

이 연구 라인의 모든 최신 알고리즘은 1990년 돈 코퍼스미스와 슈무엘 위노그라드가 제시한 코퍼스미스-위노그라드 알고리즘의 일반화인 레이저 방법을 사용하며 ^[23]2010년까지 최고의 행렬 곱셈 알고리즘이었습니다.이 알고리즘들의 개념적인 아이디어는 Strassen의 알고리즘과 유사합니다. k개 미만의³ 곱셈으로 2개의 k × k개의 행렬을 곱하는 방법이 고안되었고, 이 기법은 재귀적으로 적용됩니다.레이저 방식은 출력에 제한이 있으며 λ < 2.3725를 ^[24]표시하는 데 사용할 수 없습니다.Duan, Wu 및 Zhou는 조합 ^[3]손실이라고 하는 레이저 방법에서 잠재적 최적화의 원천을 식별합니다.그들은 이것을 이용하여 기존의 레이저 방법 알고리즘의 장벽을 깨고 ω < 2.37188을 보여주기 위해 사용하는 레이저 방법의 변형을 고안하는 방법을 찾습니다.이 새로운 접근 방식을 사용하면 Duan, Wu 및 Zhou에 따라 다른^[24] 경계가 적용되며 χ < 2.3078을 나타내는 것은 레이저 방법에서의 조합 손실만 해결할 수 없습니다.

행렬 곱셈 알고리즘의 그룹 이론 재구성

Henry Cohn, Robert Kleinberg, Baláz Szegedy, Chris Umans는 TPP(트리플 곱 속성)라고 불리는 불연성 성질을 만족시키는 유한 그룹의 부분 집합의 삼중항을 사용함으로써 Strassen과 Coppersmith-Winograd 알고리즘과 같은 방법을 완전히 다른 그룹 이론적 맥락에 놓았습니다.그들은 또한 만약 사실이라면, 본질적으로 2차 복잡성을 가진 행렬 곱셈 알고리즘이 있다는 것을 의미하는 추측을 제공합니다.이것은 행렬 곱셈의 최적 지수가 2라는 것을 의미하며, 대부분의 연구자들이 실제로 ^[5]그러하다고 믿고 있습니다.그러한 추측 중 하나는 대칭 그룹을 가진 아벨 그룹의 화환 제품 패밀리가 ^[25][26]TPP의 동시 버전으로 하위 집합 트리플 패밀리를 실현한다는 것입니다.그들의 추측 중 몇 가지는 Blasiak, Cohn, Church, Grochow, Naslund, Sawin, Umans에 의해 슬라이스 랭크 ^[27]방법을 사용하여 증명되었습니다.또한 Alon, Shpilka 및 Chris Umans는 최근 빠른 행렬 곱셈을 암시하는 이러한 추측 중 일부가 또 다른 그럴듯한 추측인 해바라기 ^[28]추측과 양립할 수 없다는 것을 보여주었고, 이는 다시 캡 세트 [27]문제와 관련이 있습니다.

ω의 하한

ω 2 ${\displaystyle \omega \geq$ 2$\}$의 사소한 하한이 있습니다. 두 n × n 행렬을 곱하는 알고리즘은 모든 2n 개의 항목을 처리해야 하므로, 행렬 곱셈 알고리즘에 대한 ω${\displaystyle (}$n) 연산의 사소한 점근적 하한이 있습니다. 2 ω < 2{\$displaystyle$ 2$\leq \omega$<$2.37188$ω > {\$displaystyle \omega$> $2$ 여부를 알 수 없습니다.행렬 곱셈 복잡도에 대한 가장 잘 알려진 하한은 실수 또는 복소수에 대한 경계 계수 산술 회로에 대한 Ω(n² log(n))이며 Ran ^[29]Raz에 기인합니다.

지수 δ는 전체 행렬 곱셈 알고리즘에서 지수의 최솟값이라는 점에서 한계점으로 정의됩니다.이 한계점은 달성되지 않은 것으로 알려져 있습니다.즉, 일반적으로 연구되는 계산 모델 하에서 정확하게 O^ω(n) 연산을 사용하는 행렬 곱셈 알고리즘은 존재하지 않으며,^[15] n의^o(1) 추가적인 인자가 있어야 합니다.

직사각형 행렬 곱셈

직사각형 행렬 곱셈에도 유사한 기법이 적용됩니다.연구의 중심 개체는${\displaystyle }$ω ( k${\displaystyle )}${\$displaystyle \omega(k$${\displaystyle {}^{}}$가${\displaystyle }$⌈ ${\displaystyle n^{}}$ k${\displaystyle }$⌉ ${\displaystyle n^{}}$ ⌉ $\times$$\lceil$ n^{$k}\rceil$$}$인 행렬을 O$n$c +$o (1) {\displaystyle$c}와 곱할 수 있는 가장 $작은$ c$$${\$$displaystyle$ c$}$입니다.대수적 복잡성의 결과는 $크기{\displaystyle }$n ×${\displaystyle {}^{}}$ ${\displaystyle k^{}}$${\displaystyle {}^{}}$$∈$ {\$displaystyle$ n$\times \lceil$ n$^{k}\rceil$ $}$와${\displaystyle {크기}^{}}$ ${\displaystyle {}^{}}$${\displaystyle }$× ${\displaystyle n}${\$displaystyle$ \$lceil$$n^{$k}\$rceil$ \$times$ n$}$과 $크기{\displaystyle }$n${\displaystyle }$× ${\displaystyle n^{}}$ ${\$$displaystyle$n$\times$ \$n\$times n\times n\displaystyle n$^{k}\$$rceil$$$$}$의 곱셈 행렬과 동일한 수의 산술 연산이 필요함을 나타냅니다.$크기 n$ × n${\$$displaystyle$n\$times$n}, $크기$${\displaystyle }$n × ${\displaystyle n}$ ${\displaystyle$ n\times n}, n${\displaystyle }$× ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ $⌉$ {\$displaystyle$ n$\times$ \$lceil$ n$^{k}\rceil$ $\}$이므로 이는 직사각형 행렬 곱셈의 복잡도를 포함합니다.이것은${\displaystyle }$ω (${\displaystyle 1)}$ =$$ω {\$displaystyle$\omega ($1$=\$omega$ $\}$이기 때문에 제곱 행렬 곱셈 지수를 일반화합니다.

행렬 곱셈 문제의 출력은 $크기$ n ${\displaystyle 2^{}}${\$displaystyle$ n$^{2$이므로, k$${\$displaystyle$ k$\}$의 모든 값에 대하여${\displaystyle }$ω (${\displaystyle k)}$ ≥ ${\displaystyle \omega$ ($k)\geq$2}가 있습니다. 만약 0과 1 사이의 k$${\$displaystyle$ k$}$의 $일부$ 값에 대하여${\displaystyle }$ω (${\displaystyle k)}$ ${\displaystyle \le }$ ${\displaystyle \omega$ ($k)\leq$ 2$\}$임을 증명할 수 있다면,그런 다음 이 k ${\displaystyle$ k$\}$에 대해${\displaystyle }$ω ( ${\displaystyle k)}$ = ${\displaystyle 2}${\$displaystyle \omega$ ($k)$ = $2}$임을 보여줍니다.ω${\displaystyle }$( ${\displaystyle k)}$ =$$2 ${\displaystyle$$$\$omega ($k) =$$$2}$와 ${\displaystyle \mathrm{같은}}$ 가장 큰 k는 이중 행렬 곱셈 지수로 알려져 있으며, 보통 α로 표시됩니다. α는 ${\displaystyle \mathrm{\alpha }}$ =$$1 {\$displaystyle$ \$alpha$= 1}이 ω =$$2 {\$displaystyle$ \$omega$ =$$2$}$임을 보여주는 것과 동일하기 때문에 "π"로 불립니다. 행렬 곱셈 지수와 마찬가지로,이중 행렬 곱셈 지수는 수치 선형 대수와 ^[31]최적화에서 알고리즘의 복잡성에 때때로 나타납니다.

α에 대한 첫 번째 경계는 1982년 코퍼스미스에 의한 것으로, 그는가 0{\$displaystyle \alpha >0.17227$^[32]을 보여주었습니다.α에 대한 현재 최고의 동료 검토 경계는 Le Gall과 Urutia에 ^[33]의해 주어진α > {\$displaystyle \alpha >0.31389$입니다.이 논문은 또한${\displaystyle }$ω ( k${\displaystyle )}${\$displaystyle \omega(k$에 대한 경계를 포함합니다. 2023년 7월에 Williams, Xu, Xu, Zhou는 사전 인쇄에서 α ≥ ${\displaystyle 0.321334}${\$displaystyle \alpha \geq$ 0$.321334}$를 $보여준다고$ 주장합니다.

관련문제

행렬 곱셈과 동일한 점근적 복잡성을 갖는 문제에는 행렬식, 행렬 반전, 가우스 제거(다음 섹션 참조)가 포함됩니다.ω ${\displaystyle \omega$}로$$표현할 수 있는 복잡성 문제에는 특성 다항식, 고유 값(고유 벡터는 아님), 헤르마이트 정규 형식 및 스미스 정규 형식이 포함됩니다.

행렬 반전, 행렬식 및 가우스 소거

Strassen은 1969년 논문에서 행렬 계산에 대한 $복잡도{\displaystyle }$O (${\displaystyle {n_{}}^{}}$ ${\displaystyle {{log\mathrm{}}_{}}^{}}$ 2 ${\displaystyle {{}_{}}^{}{7}^{}}$ ) ${\displaystyle \ge O}$ (${\displaystyle n^{}}$ 2${\displaystyle {.807}^{}}${\$displaystyle$O($n^{\log$ _${2}7})\$arx O$(n^{2.807})}$를 증명한 바 있습니다.증명은 사용되는 행렬 곱셈에 대해 그 복잡도가${\displaystyle }$O (${\displaystyle {}^{}}$ω )$${\$displaystyle O$$(n^{\omega$$$})}인 일부${\displaystyle }$ω ≥$$≥ any the \displaystyle \$geq$ 2$}$에 대한 것을 제외하고는 어떤 가정도 하지 않습니다.

Strassen 증명의 시작점은 블록 행렬 곱셈을 사용하는 것입니다.구체적으로, 짝수 차원 2nx2n의 행렬은 4개의 nxn 블록으로 분할될 수 있음

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

이 형태에서, 그것의 역은

${\displaystyle {\display{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{\displaystyle }$ - ${\displaystyle {\mathrm{CA}}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}${\$displaystyle {D}-{CA}^{-1}{B}}$이(가) 반전 가능한 경우.

따라서 2nx2n 행렬의 역은 nxn 행렬의 2개의 역, 6개의 곱셈 및 4개의 덧셈 또는 덧셈 역으로 계산할 수 있습니다.다음은 각각 I(n), M(n), A(n) = n×n 행렬의 반전, 곱셈 및 덧셈에 필요한 연산의 수를 나타내는 것입니다.

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

n = ${\displaystyle {}^{}}$ ${\displaystyle k^{}}${\$displaystyle$ n = $2^{k}}$인 경우 이 공식을 재귀적으로 적용할 수 있습니다.

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

$만약{\displaystyle M}$( n )${\displaystyle }$≤ ${\displaystyle {cn}^{}}$≥$$, {\$displaystyle M(n$)\$leq$ cn$^{\$omega$}},$ ${\displaystyle {}^{}}$= ${\displaystyle 2^{}\ge }$ $,$ ${\displaystyle$ \$alpha$ = 2^{\$omega}\geq$ 4$,}$ 결국 얻어집니다.

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

일정한 기간 동안

차원이 2의 거듭제곱이 아닌 행렬의 경우 행렬의 차원을 2의 거듭제곱으로 늘리면 동일한 복잡도에 도달합니다. 행렬에는 대각선에 항목이 1이고 다른 곳에는 0인 행과 열이 추가됩니다.

이것은 반전되어야 하는 모든 부분 행렬이 실제로 가역적이라는 행렬에 대한 주장된 복잡성을 증명합니다.따라서 임의로 선택된 항목이 있는 행렬은 확률 1과 가역적이기 때문에 이 복잡성은 거의 모든 행렬에서 증명됩니다.

행렬 A가 가역일 경우 등식이 LU 분해에도 동일한 인수가 적용됩니다.

${\displaystyle {\display{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}}$

A ${\displaystyle$ A$}$ 및$$${\displaystyle }D{\displaystyle }$ - ${\displaystyle {}^{}}$- ${\displaystyle {}^{}}$ B${\displaystyle ,}$ ${\displaystyle D-CA^{-1}B,}$에 재귀적으로 적용할 수 있는 블록 LU 분해를 정의합니다.

이 인수는 다음과 같은 블록 LU 분해로 인해 발생하므로 행렬식에도 적용됩니다.

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

곱셈 횟수 최소화

산술 연산의 수를 최소화하는 문제와 관련하여 곱셈의 수를 최소화하는 것은 일반적으로 덧셈보다 비용이 많이 드는 연산입니다.행렬 곱셈에 대한 O${\displaystyle ({}^{}}$ω )$${\$displaystyle$ O$(n^{\omega})}$ $알고리즘$은 반드시 O${\displaystyle ({}^{}}$ω )$${\$displaystyle$ O$(n^{\omega})}$ 곱셈 연산만 $사용$해야 하지만 이러한 알고리즘은 실용적이지 않습니다.교과서 곱셈을 위한 ${\displaystyle {순진}^{}}$한 3$${\$displaystyle$ n$^{3}$ 곱셈에서$$ $Z{\displaystyle \mathrm{}}$${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle Z\mathbb{}}${\$displaystyle \mathbb {Z}$ / $2\mathbb {Z}}$의 4${\displaystyle \times 4}${\$displaystyle$ 4$\times$ 4$}$ 행렬은$$ 47개의 ^[34]곱셈으로 수행할 수 있습니다.${\displaystyle 3}$× ${\displaystyle 3}$ ${\displaystyle$ 3$\times$ 3$}$ 행렬$$ 곱셈은 교환 링에 대해 21번의^[35][36] 곱셈(비교환인^[37] 경우 23번)으로 수행할 수 있습니다.필요한 곱셈의 하한은 2mn+2n-m-2(대체 방법, m⩾n⩾3을 사용하여 n×mmatrices와 m×nmatrices의 곱셈)이며, 이는 n=3인 경우 최소 19개의 곱셈과 n=4개 이상의 34개의 곱셈이 필요함을 의미합니다.n=2개의 최적 7개 곱셈의 경우 8개 곱셈의 경우 4개의 덧셈에 비해 15개의 덧셈은 최소입니다.

참고 항목

• 수학 연산의 계산 복잡도
• CYK 알고리즘, §Valiant's 알고리즘
• 주어진 행렬 A, B, C가 AB = C인 경우 Ω(n) 시간 내에 검증하는 간단한 몬테카를로 알고리즘인 Freivalds 알고리즘.
• 행렬 연쇄 곱셈
• 추상적 정의의 경우 행렬 곱셈
• 매트릭스 곱셈 알고리즘(Matrix Multiple Algorithm), 실제 구현 세부 정보 제공
• 희소 행렬-벡터 곱셈

참고문헌

외부 링크

• 빠른 행렬 곱셈 알고리즘의 또 다른 카탈로그
• Fawzi, A.; Balog, M.; Huang, A.; Hubert, T.; Romera-Paredes, B.; Barekatain, M.; Novikov, A.; Ruiz, F.J.R.; Schrittwieser, J.; Swirszcz, G.; Silver, D.; Hassabis, D.; Kohli, P. (2022). "Discovering faster matrix multiplication algorithms with reinforcement learning". Nature. 610 (7930): 47–53. Bibcode:2022Natur.610...47F. doi:10.1038/s41586-022-05172-4. PMC 9534758. PMID 36198780.