Strassen algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. november 2021; checks kræver 20 redigeringer .

Strassens algoritme er designet til hurtig matrixmultiplikation . Den blev udviklet af Volker Strassen i 1969 og er en generalisering af Karatsubas metode til matrixmultiplikation.

I modsætning til den traditionelle matrixmultiplikationsalgoritme (ifølge formlen ), der kører i tid , multiplicerer Strassen-algoritmen matricer i tid , hvilket giver en gevinst på store tætte matricer. ${\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)))$

På trods af at Strassens algoritme asymptotisk ikke er den hurtigste af de eksisterende hurtigmatrixmultiplikationsalgoritmer, er den nemmere at programmere og mere effektiv når man multiplicerer relativt små matricer, så det er den der oftest bruges i praksis.

Beskrivelse af algoritmen

Hvis vi tilføjer de samme nulrækker og kolonner til matricerne , bliver deres produkt lig med matrixen med de samme tilføjede rækker og kolonner. Derfor kan kun matricer af størrelse tages i betragtning , og andre tilfælde kan reduceres til dette ved at tilføje nuller, som kun kan fordobles. $EN$ $B$ $AB$ ${\displaystyle n=2^{k},\ k\in {\mathbb {N} ))$ $n$

Lad være matricer af størrelse . De kan repræsenteres som blokmatricer af størrelse fra -matricer: $A,B$ ${\displaystyle 2^{k}\ gange 2^{k))$ $(2\ gange 2)$ $(2^{k-1}\ gange 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}}

Ved princippet om blokmultiplikation udtrykkes en matrix i form af deres 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}}\ ,

hvor der på højre side er otte multiplikationer af matricer af størrelse . Da matricerne danner en ring , er enhver algoritme til multiplikation af -matricer, der kun bruger additioner, subtraktioner og multiplikationer, egnet til at beregne højre side. Strassen foreslog følgende algoritme med syv multiplikationer: $2^{k-1}\ gange 2^{k-1}$ $(2\ gange 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}}

Hver multiplikation kan udføres rekursivt ved hjælp af den samme procedure, og addition kan udføres trivielt ved at tilføje elementer. Derefter estimeres køretiden for algoritmen gennem den rekursive relation : $(2^{k-1})^{2}$ $T(n)$

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

Implementeringseksempel

Nedenfor er et eksempel på implementering af algoritmen i Python ved hjælp af NumPy- biblioteket til hurtigt at tage submatricer. Hovedfunktionen er strassen_mul. Alle matricer antages at være kvadratiske, repræsenteret ved type numpy.array, og deres størrelse er en potens af 2.

For små matrixstørrelser er direkte multiplikation hurtigere end Strassen-algoritmen på grund af det store antal tilføjelser i sidstnævnte. Grænsen for sådanne størrelser afhænger af forholdet mellem tidspunktet for addition og multiplikation af elementer og kan derfor variere afhængigt af hardwaremiljøet. I koden er konstanten ansvarlig for sit formål TRIVIAL_MULTIPLICATION_BOUND.

fra itertools import produkt import numpy som np def split_to_2x2_blocks ( matrix ): returliste ( map ( lambda row : np . hsplit ( row , 2 ), np . vsplit ( matrix , 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 ]) venstre = strassen_mul ( lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] - rb [ 0 ][ 0 ]) højre = strassen_mul ( lb [ 0 ][ 0 ], rb [ 0 ][ 1 ] - rb [ 1 ][ 1 ]) top = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 0 ][ 1 ], rb [ 1 ][ 1 ]) bund = strassen_mul ( lb [ 1 ][ 0 ] + lb [ 1 ] [ 1 ], rb [ 0 ][ 0 ]) returner [[ d + d_1 + venstre - top , højre + top ], [ venstre + bund , d + d_2 + højre - bund ]] def trivial_mul ( venstre , højre ): højde , mellemstørrelse = venstre . form mid_size , højre = højre . former resultat = np . nuller (( højde , bredde )) for række , kolonne , midt i produktet ( * kort ( rækkevidde , [ højde , bredde , mellemstørrelse ])): resultat [ række ][ col ] += venstre [ række ][ midt ] * højre [ midt ][ col ] returnere resultat TRIVIAL_MULTIPLICATION_BOUND = 8 def strassen_mul ( venstre , højre ): hævde ( venstre . form == højre . form ) hævde ( venstre . form [ 0 ] == venstre . form [ 1 ]) hvis venstre . form [ 0 ] <= TRIVIAL_MULTIPLICATION_BOUND : returner trivial_mul ( venstre , højre ) hævde ( venstre form [ 0 ] % 2 == 0 ) returnere np . _ blok ( strassen_mul_2x2 ( * kort ( split_to_2x2_blocks , [ left , right ]))) )

Videreudvikling

Strassen var den første til at vise muligheden for at multiplicere matricer på en mere effektiv måde end standarden. Efter udgivelsen af hans arbejde i 1969 begyndte en aktiv søgen efter en hurtigere algoritme. Den mest asymptotisk hurtige algoritme i dag er Coppersmith-Winograd-algoritmen , som giver dig mulighed for at multiplicere matricer i operationer [1] , foreslået i 1987 og forbedret i 2011 til niveauet [1] . Denne algoritme er uden praktisk interesse på grund af den astronomisk store konstant i estimering af den aritmetiske kompleksitet. Spørgsmålet om den asymptotisk begrænsende hastighed for matrixmultiplikation er ikke blevet løst. Der er Strassens formodning om, at for tilstrækkeligt store er der en algoritme til at multiplicere to matricer af størrelse i operationer, hvor et forudtildelt positivt tal er vilkårligt lille. Denne formodning er af rent teoretisk interesse, da størrelsen af matricer, som den er virkelig lille til, tilsyneladende er meget stor. ${{\rm {O}}}(n^{{2.376}})$ ${{\rm {O}}}(n^{{2.3727}})$ $n$ $n\ gange n$ ${{\rm {O}}}(n^{{2+\varepsilon }})$ $\varepsilon$ $\varepsilon$

Spørgsmålet om at konstruere den hurtigste og mest stabile praktiske algoritme til at multiplicere store matricer forbliver også uløst.

Winograd-Strassen algoritme

Der er en modifikation af Strassen-algoritmen, der kræver 7 multiplikationer og 15 additioner (i stedet for 18 for den almindelige Strassen-algoritme).

Matricerne er opdelt i blokundermatricer som vist ovenfor. $A,\,B,\,C$

Mellemelementer beregnes $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}}

Matrixelementer beregnes som følger: $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}}.

Den aktuelle tilstand af problemet

Strassens algoritme er en bilineær algoritme, dens koefficienter er rødderne til det kubiske system af Brents ligninger . [2] For klassen af eksakte algoritmer <2x2x2> er dette et minimalt problem, hvis løsning gør det muligt at reducere antallet af multiplikationer i ringen af matrixelementer. [3] [4] Problemet med at finde nye algoritmer er, at Brent-systemet er ikke-lineært, antallet af ukendte og ligninger (disse tal falder ikke sammen) vokser hurtigt med størrelsen af matricerne, og kun løsninger med en stor antal nuller er påkrævet.

I 2013, efter delvis at overvinde disse problemer, var det muligt at finde den første praktiske bilineære algoritme til matrixmultiplikation, som er asymptotisk hurtigere end Strassen-algoritmen. [5] Smirnovs algoritme <3x3x6; 40> multiplicerer en 3X3 matrix med en 3x6 matrix ved hjælp af 40 multiplikationer i stedet for 54. Dens asymptotiske kompleksitet er . (Tensormultiplikation af algoritmen i sig selv med et cyklisk skift af argumenter fører til en algoritme for kvadratiske matricer <54x54x54; 64000> med samme kompleksitet). For en reel acceleration af multiplikation kræves betydelig optimering - fjernelse af mange duplikerede beregninger i lineære former. $O(n^{\log _{54}64000})=O(n^{2,78})$

I dag (2022) er dette asymptotisk den hurtigste praktiske bilineære algoritme for et vilkårligt felt af matrixelementer.

Den 5. oktober 2022 fandt DeepMind, ved hjælp af AlphaZero neurale netværksalgoritmen, flere nye algoritmer til at multiplicere matricer af forskellige dimensioner. Imidlertid er deres hastighed for et vilkårligt felt langt fra hastigheden af kendte bedste algoritmer. Så for 4X4-matricer kræver Strassen-algoritmen 49 multiplikationer, og AlphaTensor fandt en algoritme, der kræver 47 multiplikationer, men den virker kun for feltet . [6] [7] $\mathbb{Z } _{2}$

Noter

↑ 1 2 Matematikere har overvundet kobbersmed-Winograd-barrieren . lenta.ru (12. december 2011). Dato for adgang: 12. december 2011. Arkiveret fra originalen 5. februar 2012. (ubestemt)
↑ RPBrent. Algoritmer til matrixmultiplikationer// Datalogi afd. Rapport CS 157, Stanford University, 1970.
↑ Kompleksiteten af matrix multiplikation. Anmeldelse//Kybernetisk. kollektion. 1988. Udgave. 25. S. 139-236.
↑ Landsberg JM Geometri og kompleksiteten af matrixmultiplikation // Bull. amer. Matematik. soc. 2008. V.45. s. 247-284.
↑ A. V. Smirnov, “Om bilineær kompleksitet og praktiske algoritmer til matrixmultiplikation”, Zh. Vychisl. matematik. og mat. Fiz., 53:12 (2013), 1970-1984; Comput. Matematik. Matematik. Phys., 53:12 (2013), 1781-1795
↑ Opdagelse af nye algoritmer med AlphaTensor . www.deepmind.com . Hentet: 6. oktober 2022.
↑ Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Opdagelse af hurtigere matrixmultiplikationsalgoritmer med forstærkningslæring // Nature . — 2022-10. — Bd. 610 , udg. 7930 . — S. 47–53 . — ISSN 1476-4687 . - doi : 10.1038/s41586-022-05172-4 .

Litteratur

Strassen V. Gaussian Elimination er ikke 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. Dekomponeringsmetode: Multiplikation af store heltal og Strassen matrix multiplikationsalgoritmen // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 189-195. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 28. Arbejde med matricer // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. — 2. udgave. - M . : "Williams" , 2005. - S. 833 - 839. - ISBN 5-8459-0857-4 .