Strassen algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 november 2021; kontroller kräver 20 redigeringar .

Strassens algoritm är designad för snabb matrismultiplikation . Den utvecklades av Volker Strassen 1969 och är en generalisering av Karatsubas metod för matrismultiplikation.

Till skillnad från den traditionella matrismultiplikationsalgoritmen (enligt formeln ) som körs i tid , multiplicerar Strassen-algoritmen matriser i tid , vilket ger en vinst på stora täta matriser. ${\displaystyle c_{ij}=\sum a_{ik}b_{kj))$ $\Theta (n^{{\log _{2}8)))=\Theta (n^{3})$ $\Theta (n^{{\log _{2}7)))=O(n^{{2.81)))$

Trots att Strassens algoritm asymptotiskt sett inte är den snabbaste av de befintliga snabbmatrismultiplikationsalgoritmerna är den lättare att programmera och effektivare när man multiplicerar relativt små matriser, så det är den som oftast används i praktiken.

Beskrivning av algoritmen

Om vi lägger till samma nollrader och kolumner till matriserna blir deras produkt lika med matrisen med samma tillagda rader och kolumner. Därför kan endast matriser av storlek beaktas , och andra fall kan reduceras till detta genom att lägga till nollor, som bara kan fördubblas. $A$ $B$ $AB$ ${\displaystyle n=2^{k},\ k\in {\mathbb {N} ))$ $n$

Låt vara matriser av storlek . De kan representeras som blockmatriser av storlek från -matriser: $A,B$ ${\displaystyle 2^{k}\times 2^{k))$ $(2\ gånger 2)$ $(2^{k-1}\times 2^{k-1})$

A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix)),\quad B={\begin{pmatrix}B_{11} &B_{12}\\B_{21}&B_{22}\end{pmatrix}}

Genom principen om blockmultiplikation uttrycks en matris i termer av deras produkt $AB$

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

där på höger sida finns åtta multiplikationer av matriser av storlek . Eftersom matriserna bildar en ring är vilken algoritm som helst för att multiplicera -matriser som endast använder additioner, subtraktioner och multiplikationer lämplig för att beräkna höger sida. Strassen föreslog följande algoritm med sju multiplikationer: $2^{k-1}\times 2^{k-1}$ $(2\ gånger 2)$

{\begin{aligned}D&=(A_{11}+A_{22})(B_{11}+B_{22});\\D_{1}&=(A_{12}-A_{ 22})(B_{21}+B_{22});\\D_{2}&=(A_{21}-A_{11})(B_{11}+B_{12});\\H_{ 1}&=(A_{11}+A_{12})B_{22};\\H_{2}&=(A_{21}+A_{22})B_{11};\\V_{1} &=A_{22}(B_{21}-B_{11});\\V_{2}&=A_{11}(B_{12}-B_{22});\\\end{aligned}}

{\begin{aligned}AB&={\begin{pmatrix}D&0\\0&D\end{pmatrix}}+{\begin{pmatrix}D_{1}&0\\0&D_{2}\end{pmatrix} }+{\begin{pmatrix}-H_{1}&H_{1}\\H_{2}&-H_{2}\end{pmatrix}}+{\begin{pmatrix}V_{1}&V_{2} \\V_{1}&V_{2}\end{pmatrix}}\\&={\begin{pmatrix}D+D_{1}+V_{1}-H_{1}&V_{2}+H_{1 }\\V_{1}+H_{2}&D+D_{2}+V_{2}-H_{2}\end{pmatrix}}\ .\end{aligned}}

Varje multiplikation kan göras rekursivt med samma procedur, och addition kan göras trivialt genom att lägga till element. Sedan uppskattas algoritmens gångtid genom den rekursiva relationen : $(2^{k-1})^{2}$ $T(n)$

T(n)=7T(n/2)+O(n^{2})=O(n^{\log _{2}7})\ .

Implementeringsexempel

Nedan är ett exempel på implementering av algoritmen i Python som använder NumPy- biblioteket för att snabbt ta submatriser. Huvudfunktionen är strassen_mul. Alla matriser antas vara kvadratiska, representerade av typ numpy.array, och deras storlek är en potens av 2.

För små matrisstorlekar är direkt multiplikation snabbare än Strassen-algoritmen på grund av det stora antalet tillägg i den senare. Gränsen för sådana storlekar beror på förhållandet mellan tidpunkten för addition och multiplikation av element och kan därför variera beroende på hårdvarumiljön. I koden är konstanten ansvarig för sitt syfte TRIVIAL_MULTIPLICATION_BOUND.

från itertools importera produkt importera numpy som np def split_to_2x2_blocks ( matris ): returlista ( karta ( lambda rad : np . hsplit ( rad , 2 ), np . vsplit ( matris , 2 ) ) ) def strassen_mul_2x2 ( lb , rb ): d = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 1 ][ 1 ], rb [ 0 ][ 0 ] + rb [ 1 ][ 1 ]) d_1 = strassen_mul ( lb [ 0 ][ 1 ] - lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] + rb [ 1 ][ 1 ]) d_2 = strassen_mul ( lb [ 1 ][ 0 ] - lb [ 0 ][ 0 ], rb [ 0 ][ 0 ] + rb [ 0 ][ 1 ]) vänster = strassen_mul ( lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] - rb [ 0 ][ 0 ]) höger = strassen_mul ( lb [ 0 ][ 0 ], rb [ 0 ][ 1 ] - rb [ 1 ][ 1 ]) topp = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 0 ][ 1 ], rb [ 1 ][ 1 ]) botten = strassen_mul ( lb [ 1 ][ 0 ] + lb [ 1 ] [ 1 ], rb [ 0 ][ 0 ]) returnera [[ d + d_1 + vänster - topp , höger + topp ], [ vänster + botten , d + d_2 + höger - botten ]] def trivial_mul ( vänster , höger ): höjd , mid_size = vänster . form mid_size , höger = höger . former resultat = np . nollor (( höjd , bredd )) för rad , kol , mitt i produkten ( * karta ( intervall , [ höjd , bredd , mellanstorlek ])): resultat [ rad ][ kol ] += vänster [ rad ][ mitten ] * höger [ mitten ][ kol ] returnera resultatet TRIVIAL_MULTIPLICATION_BOUND = 8 def strassen_mul ( vänster , höger ): hävda ( vänster . form == höger . form ) hävda ( vänster . form [ 0 ] == vänster . form [ 1 ]) om kvar . form [ 0 ] <= TRIVIAL_MULTIPLICATION_BOUND : returnera trivial_mul ( vänster , höger ) hävda ( vänster . form [ 0 ] % 2 == 0 ) returnera np . block ( strassen_mul_2x2 ( * karta ( split_to_2x2_blocks , [ left , right ]))) )

Vidareutveckling

Strassen var först med att visa möjligheten att multiplicera matriser på ett mer effektivt sätt än standarden. Efter publiceringen av hans arbete 1969 började ett aktivt sökande efter en snabbare algoritm. Den mest asymptotiskt snabba algoritmen idag är Coppersmith-Winograd-algoritmen , som låter dig multiplicera matriser i operationer [1] , som föreslogs 1987 och förbättrades 2011 till nivån [1] . Denna algoritm har inget praktiskt intresse på grund av den astronomiskt stora konstanten för att uppskatta den aritmetiska komplexiteten. Frågan om den asymptotiskt begränsande hastigheten för matrismultiplikation har inte lösts. Det finns Strassens gissning att för tillräckligt stora finns en algoritm för att multiplicera två matriser av storlek i operationer, där ett förtilldelat positivt tal är godtyckligt litet. Denna gissning är av rent teoretiskt intresse, eftersom storleken på matriser, för vilka den verkligen är liten, uppenbarligen är mycket stor. ${{\rm {O}}}(n^{{2.376}})$ ${{\rm {O}}}(n^{{2.3727}})$ $n$ $n\ gånger n$ ${{\rm {O}}}(n^{{2+\varepsilon }})$ $\varepsilon$ $\varepsilon$

Frågan om att konstruera den snabbaste och mest stabila praktiska algoritmen för att multiplicera stora matriser förblir också olöst.

Winograd-Strassen algoritm

Det finns en modifiering av Strassen-algoritmen som kräver 7 multiplikationer och 15 additioner (istället för 18 för den vanliga Strassen-algoritmen).

Matriserna är uppdelade i blocksubmatriser som visas ovan. $A,\,B,\,C$

Mellanliggande element beräknas $S_{1},\,\ldots ,\,S_{8},\,P_{1},\,\ldots ,\,P_{7},\,T_{1},\,T_{ 2}$

{\begin{aligned}S_{1}&=(A_{21}+A_{22});\\S_{2}&=(S_{1}-A_{11});\\S_ {3}&=(A_{11}-A_{21});\\S_{4}&=(A_{12}-S_{2});\\S_{5}&=(B_{12} -B_{11});\\S_{6}&=(B_{22}-S_{5});\\S_{7}&=(B_{22}-B_{12});\\S_ {8}&=(S_{6}-B_{21});\\P_{1}&=S_{2}S_{6};\\P_{2}&=A_{11}B_{11} ;\\P_{3}&=A_{12}B_{21};\\P_{4}&=S_{3}S_{7};\\P_{5}&=S_{1}S_{5 };\\P_{6}&=S_{4}B_{22};\\P_{7}&=A_{22}S_{8};\\T_{1}&=P_{1}+P_ {2};\\T_{2}&=T_{1}+P_{4}.\end{aligned}}

Matriselement beräknas enligt följande: $C$

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}}={\begin{pmatrix}P_{2}+P_{3}&T_ {1}+P_{5}+P_{6}\\T_{2}-P_{7}&T_{2}+P_{5}\end{pmatrix}}.

Det aktuella läget för problemet

Strassens algoritm är en bilinjär algoritm, dess koefficienter är rötterna till det kubiska systemet av Brents ekvationer . [2] För klassen av exakta algoritmer <2x2x2> är detta ett minimalt problem, vars lösning gör det möjligt att minska antalet multiplikationer i ringen av matriselement. [3] [4] Problemet med att hitta nya algoritmer är att Brent-systemet är icke-linjärt, antalet okända och ekvationer (dessa siffror sammanfaller inte) växer snabbt med storleken på matriserna, och endast lösningar med en stor antal nollor krävs.

År 2013, efter att delvis övervinna dessa problem, var det möjligt att hitta den första praktiska bilinjära algoritmen för matrismultiplikation, som är asymptotiskt snabbare än Strassen-algoritmen. [5] Smirnovs algoritm <3x3x6; 40> multiplicerar en 3X3-matris med en 3x6-matris med 40 multiplikationer istället för 54. Dess asymptotiska komplexitet är . (Tensormultiplikation av algoritmen i sig själv med en cyklisk förskjutning av argument leder till en algoritm för kvadratiska matriser <54x54x54; 64000> med samma komplexitet). För en verklig acceleration av multiplikation krävs betydande optimering - borttagning av många dubbletter av beräkningar i linjära former. $O(n^{\log _{54}64000})=O(n^{2.78})$

Idag (2022) är detta asymptotiskt den snabbaste praktiska bilinjära algoritmen för ett godtyckligt fält av matriselement.

Den 5 oktober 2022 hittade DeepMind, med hjälp av AlphaZero neurala nätverksalgoritm, flera nya algoritmer för att multiplicera matriser av olika dimensioner. Men deras hastighet för ett godtyckligt fält är långt ifrån hastigheten för kända bästa algoritmer. Så för 4X4-matriser kräver Strassen-algoritmen 49 multiplikationer, och AlphaTensor hittade en algoritm som kräver 47 multiplikationer, men den fungerar bara för fältet . [6] [7] $\mathbb{Z } _{2}$

Anteckningar

↑ 1 2 Matematiker har övervunnit Coppersmith-Winograd-barriären . lenta.ru (12 december 2011). Datum för åtkomst: 12 december 2011. Arkiverad från originalet den 5 februari 2012. (obestämd)
↑ RPBrent. Algoritmer för matrismultiplikationer// Datavetenskaplig inst. Rapport CS 157, Stanford University, 1970.
↑ Matrismultiplikationens komplexitet. Recension//Cybernetic. samling. 1988. Nummer. 25. S. 139-236.
↑ Landsberg JM Geometri och komplexiteten i matrismultiplikation // Bull. amer. Matematik. soc. 2008. V.45. s. 247-284.
↑ A. V. Smirnov, “Om bilinjär komplexitet och praktiska algoritmer för matrismultiplikation”, Zh. Vychisl. matematik. och matta. Fiz., 53:12 (2013), 1970–1984; Comput. Matematik. Matematik. Phys., 53:12 (2013), 1781–1795
↑ Upptäck nya algoritmer med AlphaTensor . www.deepmind.com . Hämtad: 6 oktober 2022.
↑ Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Upptäck snabbare matrismultiplikationsalgoritmer med förstärkningsinlärning // Nature . — 2022-10. — Vol. 610 , iss. 7930 . — S. 47–53 . — ISSN 1476-4687 . - doi : 10.1038/s41586-022-05172-4 .

Litteratur

Strassen V. Gaussisk eliminering är inte optimal // Antal . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - s. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
Levitin A. V. Kapitel 4. Nedbrytningsmetod: Multiplikation av stora heltal och Strassen-matrismultiplikationsalgoritmen // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 189-195. — 576 sid. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 28. Arbeta med matriser // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. — 2:a upplagan. - M . : "Williams" , 2005. - S. 833 - 839. - ISBN 5-8459-0857-4 .