Algoritmul Strassen

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 noiembrie 2021; verificările necesită 20 de modificări .

Algoritmul lui Strassen este conceput pentru multiplicarea rapidă a matricei . A fost dezvoltat de Volker Strassen în 1969 și este o generalizare a metodei Karatsuba de înmulțire a matricei.

Spre deosebire de algoritmul tradițional de înmulțire a matricei (conform formulei ) care rulează în timp , algoritmul Strassen înmulțește matricele în timp , ceea ce oferă un câștig pe matrici mari dense. $c_{ij}=\sum a_{ik}b_{kj)$ $\Theta (n^{{\log _{2}8)))=\Theta (n^{3})$ $\Theta (n^{{\log _{2}7)))=O(n^{{{2,81)))$

În ciuda faptului că algoritmul lui Strassen nu este asimptotic cel mai rapid dintre algoritmii de multiplicare rapidă a matricei existenți, este mai ușor de programat și mai eficient atunci când se înmulțesc matrici relativ mici, deci este cel mai des folosit în practică.

Descrierea algoritmului

Dacă adăugăm aceleași rânduri și coloane zero la matrice , produsul lor devine egal cu matricea cu aceleași rânduri și coloane adăugate. Prin urmare, numai matricele de dimensiune pot fi luate în considerare , iar alte cazuri pot fi reduse la aceasta prin adăugarea de zerouri, care se pot dubla doar. $A$ $B$ $AB$ $n=2^{k},\k\in {\mathbb {N} )$ $n$

Fie matrice de dimensiune . Ele pot fi reprezentate ca matrici bloc de dimensiune din -matrice: $A,B$ $2^{k}\times 2^{k)$ $(2\times 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}}

Prin principiul înmulțirii blocurilor , o matrice este exprimată în funcție de produsul lor $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}}\ ,

unde în partea dreaptă sunt opt înmulțiri de matrici de mărime . Deoarece matricele formează un inel , atunci orice algoritm de înmulțire a matricelor care utilizează numai adunări, scăderi și înmulțiri este potrivit pentru calcularea părții drepte. Strassen a propus următorul algoritm cu șapte înmulțiri: $2^{k-1}\times 2^{k-1}$ $(2\times 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{aliniat}}

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

Fiecare înmulțire se poate face recursiv folosind aceeași procedură, iar adunarea se poate face trivial prin adăugarea de elemente. Apoi timpul de rulare al algoritmului este estimat prin relația recursivă : $(2^{k-1})^{2}$ $T(n)$

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

Exemplu de implementare

Mai jos este un exemplu de implementare a algoritmului în Python folosind biblioteca NumPy pentru a prelua rapid submatrice. Funcția principală este strassen_mul. Se presupune că toate matricele sunt pătrate, reprezentate prin tip numpy.array, iar dimensiunea lor este o putere de 2.

Pentru matrice de dimensiuni mici, multiplicarea directă este mai rapidă decât algoritmul Strassen datorită numărului mare de adunări din acesta din urmă. Limita acestor dimensiuni depinde de raportul dintre timpul de adăugare și multiplicare a elementelor și, prin urmare, poate varia în funcție de mediul hardware. În cod, constanta este responsabilă pentru scopul său TRIVIAL_MULTIPLICATION_BOUND.

din itertools import product import numpy ca np def split_to_2x2_blocks ( matrice ): listă returnată ( hartă ( rând lambda : np . hsplit ( rând , 2 ), np . vsplit ( matrice , 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 ]) stânga = strassen_mul ( lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] - rb [ 0 ][ 0 ]) dreapta = strassen_mul ( lb [ 0 ][ 0 ], rb [ 0 ][ 1 ] - rb [ 1 ][ 1 ]) sus = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 0 ][ 1 ], rb [ 1 ][ 1 ]) jos = strassen_mul ( lb [ 1 ][ 0 ] + lb [ 1 ] [ 1 ], rb [ 0 ][ 0 ]) return [[ d + d_1 + stânga - sus , dreapta + sus ], [ stânga + jos , d + d_2 + dreapta - jos ]] def trivial_mul ( stânga , dreapta ): înălțime , mărime_medie = stânga . formă mid_size , dreapta = dreapta . forme rezultat = np . zerouri (( înălțime , lățime )) pentru rând , col , mijloc în produs ( * hartă ( interval , [ înălțime , lățime , mărime_ mijlocie ])): rezultat [ rând ][ col ] += stânga [ rând ][ mijloc ] * dreapta [ mijloc ][ col ] returnează rezultatul TRIVIAL_MULTIPLICATION_BOUND = 8 def strassen_mul ( stânga , dreapta ): assert ( stânga . formă == dreapta . formă ) assert ( stânga . formă [ 0 ] == stânga . formă [ 1 ]) daca a ramas . forma [ 0 ] <= TRIVIAL_MULTIPLICATION_BOUND : returnează trivial_mul ( stânga , dreapta ) assert ( stânga . form [ 0 ] % 2 == 0 ) return np . bloc ( strassen_mul_2x2 ( * hartă ( split_to_2x2_blocks , [ stânga , dreapta ]))) )

Dezvoltare ulterioară

Strassen a fost primul care a arătat posibilitatea înmulțirii matricelor într-un mod mai eficient decât cel standard. După publicarea lucrării sale în 1969, a început o căutare activă a unui algoritm mai rapid. Cel mai rapid algoritm asimptotic de astăzi este algoritmul Coppersmith-Winograd , care vă permite să multiplicați matrice în operații [1] , propus în 1987 și îmbunătățit în 2011 la nivelul [1] . Acest algoritm nu prezintă interes practic datorită constantei mari din punct de vedere astronomic în estimarea complexității aritmetice. Problema ratei de limitare asimptotic a înmulțirii matricei nu a fost rezolvată. Există conjectura lui Strassen că pentru suficient de mare există un algoritm pentru înmulțirea a două matrici de dimensiune în operații, în care un număr pozitiv prealocat este arbitrar mic. Această presupunere este de interes pur teoretic, deoarece dimensiunea matricelor, pentru care este cu adevărat mică, este aparent foarte mare. ${{\rm {O}}}(n^{{2,376}})$ ${{\rm {O}}}(n^{{{2,3727}})$ $n$ $n\ ori n$ ${{\rm {O}}}(n^{{2+\varepsilon }})$ $\varepsilon$ $\varepsilon$

Problema construirii celui mai rapid și mai stabil algoritm practic pentru multiplicarea matricelor mari rămâne, de asemenea, nerezolvată.

Algoritmul Winograd-Strassen

Există o modificare a algoritmului Strassen care necesită 7 înmulțiri și 15 adunări (în loc de 18 pentru algoritmul Strassen obișnuit).

Matricele sunt împărțite în submatrici bloc așa cum se arată mai sus. $A,\,B,\,C$

Se calculează elementele intermediare $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}}

Elementele matricei se calculează după cum urmează: $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}}.

Starea actuală a problemei

Algoritmul lui Strassen este un algoritm biliniar, coeficienții săi sunt rădăcinile sistemului cubic al ecuațiilor lui Brent . [2] Pentru clasa algoritmilor exacti <2x2x2> aceasta este o problemă minimă, a cărei soluție permite reducerea numărului de înmulțiri în inelul elementelor matriceale. [3] [4] Problema găsirii de noi algoritmi este că sistemul Brent este neliniar, numărul de necunoscute și ecuații (aceste numere nu coincid) crește rapid odată cu dimensiunea matricelor și numai soluțiile cu o valoare mare. este necesar un număr de zerouri.

În 2013, după depășirea parțială a acestor probleme, a fost posibil să se găsească primul algoritm biliniar practic pentru multiplicarea matricei, care este asimptotic mai rapid decât algoritmul Strassen. [5] Algoritmul lui Smirnov <3x3x6; 40> înmulțește o matrice 3X3 cu o matrice 3x6 folosind 40 de înmulțiri în loc de 54. Complexitatea sa asimptotică este . (Înmulțirea tensorii a algoritmului în sine cu o deplasare ciclică a argumentelor conduce la un algoritm pentru matrice pătrată <54x54x54; 64000> cu aceeași complexitate). Pentru o accelerare reală a înmulțirii, este necesară o optimizare semnificativă - eliminarea multor calcule duplicate în forme liniare. $O(n^{\log _{54}64000})=O(n^{2,78})$

Astăzi (2022) acesta este asimptotic cel mai rapid algoritm biliniar practic pentru un câmp arbitrar de elemente de matrice.

Pe 5 octombrie 2022, DeepMind, folosind algoritmul rețelei neuronale AlphaZero, a găsit câțiva algoritmi noi pentru multiplicarea matricelor de diferite dimensiuni. Cu toate acestea, viteza lor pentru un câmp arbitrar este departe de viteza celor mai buni algoritmi cunoscuți. Deci, pentru matrice 4X4, algoritmul Strassen necesită 49 de înmulțiri, iar AlphaTensor a găsit un algoritm care necesită 47 de înmulțiri, dar funcționează doar pentru câmpul . [6] [7] $\mathbb{Z } _{2}$

Note

↑ 1 2 Matematicienii au depășit bariera Coppersmith-Winograd . lenta.ru (12 decembrie 2011). Data accesului: 12 decembrie 2011. Arhivat din original pe 5 februarie 2012. (nedefinit)
↑ RPBrent. Algoritmi pentru înmulțirea matricelor// Departamentul Informatică. Raport CS 157, Universitatea Stanford, 1970.
↑ Complexitatea înmulțirii matriceale. Recenzie//Cibernetică. Colectie. 1988. Problema. 25. S. 139-236.
↑ Landsberg JM Geometria și complexitatea înmulțirii matricelor // Bull. amer. Matematică. soc. 2008. V.45. p. 247-284.
↑ A. V. Smirnov, „Despre complexitatea biliniară și algoritmii practici pentru multiplicarea matricei”, Zh. Vychisl. matematica. și mat. Fiz., 53:12 (2013), 1970–1984; Calculator. Matematică. Matematică. Phys., 53:12 (2013), 1781–1795
↑ Descoperirea unor algoritmi noi cu AlphaTensor . www.deepmind.com . Preluat: 6 octombrie 2022.
↑ Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Descoperirea unor algoritmi de multiplicare matrice mai rapidă cu învățare prin întărire // Nature . — 2022-10. — Vol. 610 , iss. 7930 . — P. 47–53 . — ISSN 1476-4687 . - doi : 10.1038/s41586-022-05172-4 .

Literatură

Strassen V. Eliminarea gaussiană nu este optimă // Numer . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
Levitin A. V. Capitolul 4. Metoda de descompunere: Înmulțirea numerelor întregi mari și algoritmul de multiplicare a matricei Strassen // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 189-195. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capitolul 28. Lucrul cu Matrici // Algoritmi: Construcție și Analiză = Introducere în Algoritmi. — ediția a II-a. - M . : „Williams” , 2005. - S. 833 - 839. - ISBN 5-8459-0857-4 .