Strassenin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. marraskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 20 muokkausta .

Strassenin algoritmi on suunniteltu nopeaan matriisin kertomiseen . Sen kehitti Volker Strassen vuonna 1969, ja se on yleistys Karatsuban matriisin kertolaskumenetelmästä.

Toisin kuin perinteinen ajassa ajava matriisin kertolaskualgoritmi (kaavan mukaan ) , Strassen-algoritmi kertoo matriiseja ajassa , mikä antaa vahvistuksen suurille tiheille matriiseille. ${\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)))$

Huolimatta siitä, että Strassenin algoritmi ei ole asymptoottisesti nopein olemassa olevista nopeista matriisin kertolaskualgoritmeista, se on helpompi ohjelmoida ja tehokkaampi kertoessaan suhteellisen pieniä matriiseja, joten se on käytännössä eniten käytetty.

Algoritmin kuvaus

Jos lisäämme samat nollarivit ja sarakkeet matriiseihin , niiden tulo tulee yhtä suureksi kuin matriisi , jossa on samat lisätyt rivit ja sarakkeet. Siksi vain matriiseja, joiden koko on , voidaan ottaa huomioon , ja muut tapaukset voidaan pienentää tähän lisäämällä nollia, jotka voivat vain kaksinkertaistua. $A$ $B$ $AB$ ${\displaystyle n=2^{k},\ k\in {\mathbb {N} ))$ $n$

Antaa olla kokoisia matriiseja . Ne voidaan esittää lohkomatriiseina , joiden koko on -matriiseista : $A, B$ ${\displaystyle 2^{k}\times 2^{k))$ ${\näyttötyyli (2\kertaa 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}}

Lohkon kertolaskuperiaatteen mukaan matriisi ilmaistaan niiden tulona $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}}\ ,

jossa oikealla puolella on kahdeksan koon matriisien kertolaskua . Koska matriisit muodostavat renkaan , niin mikä tahansa algoritmi -matriisien kertomiseen , joka käyttää vain yhteen-, vähennys- ja kertolaskuja, sopii oikean puolen laskemiseen. Strassen ehdotti seuraavaa algoritmia seitsemällä kertolaskulla: $2^{k-1}\times 2^{k-1}$ ${\näyttötyyli (2\kertaa 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{tasattu}}

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

Jokainen kertolasku voidaan tehdä rekursiivisesti käyttämällä samaa menettelyä, ja yhteenlasku voidaan tehdä triviaalisti lisäämällä elementtejä. Sitten algoritmin ajoaika arvioidaan rekursiivisen suhteen avulla : $(2^{k-1})^{2}$ $T(n)$

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

Toteutusesimerkki

Alla on esimerkki Python -algoritmin toteutuksesta, joka käyttää NumPy- kirjastoa alimatriisien nopeaan ottamiseksi. Päätoiminto on strassen_mul. Kaikkien matriisien oletetaan olevan neliömäisiä, joita edustaa tyyppi numpy.array, ja niiden koko on potenssi 2.

Pienillä matriisikokoilla suora kertolasku on nopeampi kuin Strassen-algoritmi, koska jälkimmäisessä on paljon yhteenlaskuja. Tällaisten kokojen raja riippuu elementtien lisäys- ja kertomisajan suhteesta ja voi siksi vaihdella laitteistoympäristön mukaan. Koodissa vakio vastaa tarkoituksestaan TRIVIAL_MULTIPLICATION_BOUND.

itertoolsista tuonti tuotteen tuonti numpy as np _ def split_to_2x2_blocks ( matriisi ): paluuluettelo ( kartta ( lambda rivi : np . hsplit ( rivi , 2 ), np . vsplit ( matriisi , 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 ]) vasen = strassen_mul ( lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] - rb [ 0 ][ 0 ]) oikea = strassen_mul ( lb [ 0 ][ 0 ], rb [ 0 ][ 1 ] - rb [ 1 ][ 1 ]) top = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 0 ][ 1 ], rb [ 1 ][ 1 ]) alaosa = strassen_mul ( lb [ 1 ][ 0 ] + lb [ 1 ] [ 1 ], rb [ 0 ][ 0 ]) paluu [[ d + d_1 + vasen - ylhäällä , oikea + ylhäällä ], [ vasen + alaosa , d + d_2 + oikea - alhaalla ]] def trivial_mul ( vasen , oikea ): korkeus , mid_size = vasen . muoto mid_size , oikea = oikea . muodot tulos = np . nollat (( korkeus , leveys )) riville , sarakkeeseen , tuotteen keskipisteeseen ( * kartta ( alue , [ korkeus , leveys , keskikoko ] )): tulos [ rivi ][ sarake ] += vasen [ rivi ] [ keskikohta ] * oikea [ puoliväli ][ sarake ] palauttaa tuloksen TRIVIAL_MULTIPLICATION_BOUND = 8 def strassen_mul ( vasen , oikea ): assert ( vasen . muoto == oikea . muoto ) assert ( vasen . muoto [ 0 ] == vasen . muoto [ 1 ]) jos jätetään . muoto [ 0 ] <= TRIVIAL_MULTIPLICATION_BOUND : return trivial_mul ( vasen , oikea ) väittää ( vasen . muoto [ 0 ] % 2 == 0 ) return np . lohko ( strassen_mul_2x2 ( * kartta ( split_to_2x2_blocks , [ vasen , oikea ]))) )

Jatkokehitys

Strassen osoitti ensimmäisenä mahdollisuuden kertoa matriiseja tehokkaammalla tavalla kuin tavallinen. Hänen teoksensa julkaisun jälkeen vuonna 1969 aloitettiin aktiivinen nopeamman algoritmin etsiminen. Asymptoottisesti nopein algoritmi nykyään on Coppersmith-Winograd-algoritmi , jonka avulla voit kertoa matriiseja operaatioissa [1] , ehdotettu vuonna 1987 ja parannettu vuonna 2011 tasolle [1] . Tällä algoritmilla ei ole käytännön merkitystä, koska aritmeettisen monimutkaisuuden arvioinnissa on tähtitieteellisesti suuri vakio. Kysymys asymptoottisesti rajoittavasta matriisin kertolaskunopeudesta ei ole ratkaistu. On olemassa Strassenin olettamus, että riittävän suurelle on olemassa algoritmi kahden koon matriisin kertomiseksi operaatioissa , joissa ennalta määrätty positiivinen luku on mielivaltaisen pieni. Tämä olettamus on puhtaasti teoreettisesti kiinnostava, koska matriisien koko, jolle se on todella pieni, on ilmeisesti erittäin suuri. ${{\rm {O}}}(n^{{2.376}})$ ${{\rm {O}}}(n^{{2.3727}})$ $n$ $n\ kertaa n$ ${{\rm {O}}}(n^{{2+\varepsilon }})$ $\varepsilon$ $\varepsilon$

Myös kysymys nopeimman ja vakaimman käytännön algoritmin rakentamisesta suurten matriisien kertomiseen on edelleen ratkaisematta.

Winograd-Strassen-algoritmi

Strassen-algoritmiin on tehty 7 kertolaskua ja 15 yhteenlaskua (tavallisen Strassen-algoritmin 18 sijaan).

Matriisit on jaettu lohkoalimatriiseihin, kuten yllä on esitetty. ${\näyttötyyli A,\,B,\,C}$

Välielementit lasketaan $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}}

Matriisielementit lasketaan seuraavasti: $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}}.

Ongelman nykytila

Strassenin algoritmi on bilineaarinen algoritmi, jonka kertoimet ovat Brentin yhtälöiden kuutiojärjestelmän juuria . [2] Tarkkojen algoritmien luokalle <2x2x2> tämä on minimaalinen ongelma, jonka ratkaisun avulla voidaan vähentää kertolaskujen määrää matriisielementtien renkaassa. [3] [4] Uusien algoritmien löytämisen ongelmana on, että Brent-järjestelmä on epälineaarinen, tuntemattomien ja yhtälöiden määrä (nämä luvut eivät täsmää) kasvaa nopeasti matriisien koon mukaan ja vain ratkaisut, joilla on suuri vaaditaan useita nollia.

Vuonna 2013 näiden ongelmien osittaisen voittamisen jälkeen oli mahdollista löytää ensimmäinen käytännöllinen bilineaarinen matriisin kertolaskualgoritmi, joka on asymptoottisesti nopeampi kuin Strassen-algoritmi. [5] Smirnovin algoritmi <3x3x6; 40> kertoo 3x3-matriisin 3x6-matriisilla käyttämällä 40 kertolaskua 54:n sijaan. Sen asymptoottinen monimutkaisuus on . (Algoritmin tensorikerto itsellään argumenttien syklisellä siirrolla johtaa algoritmiin neliömatriiseille <54x54x54; 64000>, jolla on sama monimutkaisuus). Kertomisen todellinen kiihtyvyys edellyttää merkittävää optimointia - monien päällekkäisten laskelmien poistamista lineaarisissa muodoissa. $O(n^{\log _{54}64000})=O(n^{2.78})$

Nykyään (2022) tämä on asymptoottisesti nopein käytännöllinen bilineaarinen algoritmi mielivaltaiselle matriisielementtien kentälle .

5. lokakuuta 2022 DeepMind löysi AlphaZero-hermoverkkoalgoritmia käyttämällä useita uusia algoritmeja eri ulottuvuuksien matriisien kertomiseen. Niiden nopeus mielivaltaisessa kentässä on kuitenkin kaukana tunnettujen parhaiden algoritmien nopeudesta. Joten 4X4-matriiseille Strassen-algoritmi vaatii 49 kertolaskua, ja AlphaTensor löysi algoritmin, joka vaatii 47 kertolaskua, mutta se toimii vain kentällä . [6] [7] $\mathbb{Z } _{2}$

Muistiinpanot

↑ 1 2 Matemaatikko on voittanut Coppersmith-Winogradin esteen . lenta.ru (12. joulukuuta 2011). Käyttöpäivä: 12. joulukuuta 2011. Arkistoitu alkuperäisestä 5. helmikuuta 2012. (määrätön)
↑ RPBrent. Algoritmit matriisikertolaskuille// Computer Science Dept. Raportti CS 157, Stanford University, 1970.
↑ Matriisikertomisen monimutkaisuus. Arvostelu//Cybernetic. kokoelma. 1988. Numero. 25. S. 139-236.
↑ Landsberg JM Geometria ja matriisin kertolaskujen monimutkaisuus // Bull. amer. Matematiikka. soc. 2008. V.45. s. 247-284.
↑ A. V. Smirnov, "Bilineaarisesta monimutkaisuudesta ja matriisin kertolaskujen käytännön algoritmeista", Zh. Vychisl. matematiikka. ja matto. Fiz., 53:12 (2013), 1970–1984; Comput. Matematiikka. Matematiikka. Phys., 53:12 (2013), 1781–1795
↑ Uusien algoritmien löytäminen AlphaTensorin avulla . www.deepmind.com . Haettu: 6.10.2022.
↑ Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Nopeampien matriisin kertolaskualgoritmien löytäminen vahvistusoppimisen avulla // Luonto . – 2022-10. — Voi. 610 , iss. 7930 . — s. 47–53 . — ISSN 1476-4687 . - doi : 10.1038/s41586-022-05172-4 .

Kirjallisuus

Strassen V. Gaussin eliminointi ei ole optimaalinen // Numero . Math / F. Brezzi - Springer Science + Business Media , 1969. - Voi. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
Levitin A. V. Luku 4. Hajotusmenetelmä: Suurten kokonaislukujen kertominen ja Strassen-matriisin kertolaskualgoritmi // Algoritmit. Johdatus kehitykseen ja analyysiin - 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. Luku 28. Työskentely matriisien kanssa // Algoritmit: Konstruointi ja analyysi = Algoritmien johdatus. – 2. painos. - M . : "Williams" , 2005. - S. 833 - 839. - ISBN 5-8459-0857-4 .