Algoritm Strassen - Strassen algorithm

În algebra liniară , algoritmul Strassen , numit după Volker Strassen , este un algoritm pentru multiplicarea matricii . Este mai rapid decât algoritmul standard de multiplicare a matricii pentru matricile mari, cu o complexitate asimptotică mai bună , deși algoritmul naiv este adesea mai bun pentru matricile mai mici. Algoritmul Strassen este mai lent decât algoritmii cunoscuți cel mai rapid pentru matricile extrem de mari, dar astfel de algoritmi nu sunt utili în practică , deoarece sunt mult mai lenti pentru matricile de dimensiuni practice.

Algoritmul lui Strassen funcționează pentru orice inel , cum ar fi plus / multiplicare, dar nu toate semirings , cum ar fi min-plus sau algebră booleană , unde algoritmul naiv încă funcționează și așa-numita multiplicare a matricei combinatorii .

Istorie

Volker Strassen a publicat acest algoritm pentru prima dată în 1969 și a dovedit că algoritmul general de multiplicare a matricei nu a fost optim. Strassen Algoritmul este doar cu puțin mai bună decât cea, dar publicarea avut ca rezultat mult mai multe cercetări despre matrice de multiplicare care a condus la mai rapid abordări, cum ar fi algoritmul Arămar-Winograd . ${\ displaystyle n ^ {3}}$

Algoritm

Coloana din stânga reprezintă multiplicarea matricei 2x2 . Înmulțirea naivă a matricei necesită o înmulțire pentru fiecare „1” din coloana din stânga. Fiecare dintre celelalte coloane reprezintă una dintre cele 7 înmulțiri din algoritm, iar suma coloanelor dă multiplicarea completă a matricei din stânga.

Fie , două matrici pătrate peste un inel , de exemplu matrici ale căror intrări sunt numere întregi sau numerele reale. Vrem să calculăm produsul matricial . În următoarea expunere a algoritmului, vom presupune că toate aceste matrici au dimensiuni care sunt puteri de două (adică ), dar acest lucru este doar conceptual necesar - în cazul în care matricile , nu sunt de tip ne putem gândi conceptual despre umplere rândurile „lipsă” și coloanele cu zerouri pentru a obține matrici cu dimensiuni de puteri de două - deși implementările reale ale algoritmului, desigur, nu vor face acest lucru în practică. ${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle {\ mathcal {R}}}$${\ displaystyle C = AB}$${\ displaystyle A, \, B, \, C \ in \ operatorname {Matr} _ {2 ^ {n} \ times 2 ^ {n}} ({\ mathcal {R}})}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle 2 ^ {n} \ times 2 ^ {n}}$

Apoi am partiție , și în mod egal de dimensiuni matrici bloc${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$

${\ displaystyle A = {\ begin {bmatrix} A_ {11} & A_ {12} \\ A_ {21} & A_ {22} \ end {bmatrix}}, \ quad B = {\ begin {bmatrix} B_ {11} & B_ {12} \\ B_ {21} & B_ {22} \ end {bmatrix}}, \ quad C = {\ begin {bmatrix} C_ {11} & C_ {12} \\ C_ {21} & C_ {22} \ end {bmatrix}}, \ quad}$

cu . Algoritmul naiv ar fi: ${\ displaystyle A_ {ij}, B_ {ij}, C_ {ij} \ in \ operatorname {Mat} _ {2 ^ {n-1} \ times 2 ^ {n-1}} ({\ mathcal {R} })}$

${\ displaystyle {\ begin {bmatrix} C_ {11} & C_ {12} \\ C_ {21} & C_ {22} \ end {bmatrix}} = {\ begin {bmatrix} A_ {11} B_ {11} + A_ {12} B_ {21} și A_ {11} B_ {12} + A_ {12} B_ {22} \\ A_ {21} B_ {11} + A_ {22} B_ {21} și A_ {21} B_ {12 } + A_ {22} B_ {22} \ end {bmatrix}}.}$

Cu această construcție nu am redus numărul de înmulțiri. Încă avem nevoie de 8 înmulțiri ale blocurilor matriciale pentru a calcula matricile, același număr de înmulțiri de care avem nevoie atunci când folosim înmulțirea matricei standard. ${\ displaystyle C_ {ij}}$

Algoritmul Strassen definește în schimb noi matrice:

${\ displaystyle {\ begin {align} M_ {1} & = (A_ {11} + A_ {22}) (B_ {11} + B_ {22}); \\ M_ {2} & = (A_ {21} } + A_ {22}) B_ {11}; \\ M_ {3} & = A_ {11} (B_ {12} -B_ {22}); \\ M_ {4} & = A_ {22} (B_ {21} -B_ {11}); \\ M_ {5} & = (A_ {11} + A_ {12}) B_ {22}; \\ M_ {6} & = (A_ {21} -A_ { 11}) (B_ {11} + B_ {12}); \\ M_ {7} & = (A_ {12} -A_ {22}) (B_ {21} + B_ {22}), \\\ end {aliniat}}}$

folosind doar 7 înmulțiri (una pentru fiecare ) în loc de 8. Putem acum să exprimăm în termeni de : ${\ displaystyle M_ {k}}$${\ displaystyle C_ {ij}}$${\ displaystyle M_ {k}}$

${\ displaystyle {\ begin {bmatrix} C_ {11} & C_ {12} \\ C_ {21} & C_ {22} \ end {bmatrix}} = {\ begin {bmatrix} M_ {1} + M_ {4} - M_ {5} + M_ {7} & M_ {3} + M_ {5} \\ M_ {2} + M_ {4} & M_ {1} -M_ {2} + M_ {3} + M_ {6} \ end {bmatrix}}.}$

Iterăm recursiv acest proces de divizare până când submatricile degenerează în numere (elemente ale inelului ). Dacă, așa cum s-a menționat mai sus, matricea originală avea o dimensiune care nu era o putere de 2, atunci produsul rezultat va avea zero rânduri și coloane la fel ca și , iar acestea vor fi apoi dezbrăcate în acest moment pentru a obține matricea (mai mică) ne-am dorit foarte mult. ${\ displaystyle {\ mathcal {R}}}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$

Implementările practice ale algoritmului lui Strassen trec la metodele standard de multiplicare a matricii pentru submatrice suficient de mici, pentru care acești algoritmi sunt mai eficienți. Punctul special de încrucișare pentru care algoritmul lui Strassen este mai eficient depinde de implementarea și hardware-ul specific. Autorii anteriori estimaseră că algoritmul lui Strassen este mai rapid pentru matrici cu lățimi cuprinse între 32 și 128 pentru implementări optimizate. Cu toate acestea, s-a observat că acest punct de încrucișare a crescut în ultimii ani și un studiu din 2010 a constatat că nici măcar un singur pas al algoritmului lui Strassen nu este adesea benefic pentru arhitecturile actuale, în comparație cu o multiplicare tradițională foarte optimizată, până când dimensiunile matricei depășesc 1000 sau mai mult, și chiar și pentru dimensiuni de matrice de câteva mii, beneficiul este de obicei marginal în cel mai bun caz (aproximativ 10% sau mai puțin). Un studiu mai recent (2016) a observat beneficii pentru matrici de 512 și un beneficiu de aproximativ 20%.

Complexitate asimptotică

Schița algoritmului de mai sus a arătat că se poate scăpa cu doar 7, în loc de 8 tradiționale, multiplicări matrice-matrice pentru subblocurile matricei. Pe de altă parte, trebuie să faceți adunări și scăderi de blocuri, deși acest lucru nu este preocupat de complexitatea generală: Adăugarea matricilor de mărime necesită doar operații, în timp ce multiplicarea este substanțial mai scumpă (în mod tradițional, operațiile de adunare sau multiplicare). ${\ displaystyle N / 2}$${\ displaystyle (N / 2) ^ {2}}$${\ displaystyle 2 (N / 2) ^ {3}}$

Întrebarea este atunci de câte operații este nevoie exact pentru algoritmii lui Strassen și cum se compară acest lucru cu multiplicarea matricei standard care ia aproximativ (unde ) operații aritmetice, adică o complexitate asimptotică . ${\ displaystyle 2N ^ {3}}$${\ displaystyle N = 2 ^ {n}}$${\ displaystyle \ Theta (N ^ {3})}$

Numărul de adunări și înmulțiri necesare în algoritmul Strassen poate fi calculat după cum urmează: fie numărul de operații pentru o matrice. Apoi, prin aplicarea recursivă a algoritmului Strassen, vedem că , pentru o constantă care depinde de numărul de adăugiri efectuate la fiecare aplicație a algoritmului. Prin urmare , adică complexitatea asimptotică pentru multiplicarea matricilor de mărime utilizând algoritmul Strassen este . Reducerea numărului de operații aritmetice vine însă la prețul unei stabilități numerice oarecum reduse , iar algoritmul necesită, de asemenea, mult mai multă memorie în comparație cu algoritmul naiv. Ambele matrice inițiale trebuie să aibă dimensiunile extinse la următoarea putere de 2, ceea ce duce la stocarea de până la patru ori mai multe elemente, iar cele șapte matrice auxiliare conțin fiecare un sfert din elementele din cele extinse. ${\ displaystyle f (n)}$${\ displaystyle 2 ^ {n} \ times 2 ^ {n}}$${\ displaystyle f (n) = 7f (n-1) + l4 ^ {n}}$${\ displaystyle l}$${\ displaystyle f (n) = (7 + o (1)) ^ {n}}$${\ displaystyle N = 2 ^ {n}}$${\ displaystyle O ([7 + o (1)] ^ {n}) = O (N ^ {\ log _ {2} 7 + o (1)}) \ approx O (N ^ {2.8074})}$

Algoritmul lui Strassen trebuie comparat cu modul „naiv” de a face multiplicarea matricei care ar necesita 8 în loc de 7 multiplicări de subblocuri. Acest lucru ar da naștere la complexitatea posi- abordarea standard: . Compararea acestor doi algoritmi arată că , asimptotic , algoritmul lui Strassen este mai rapid: există o dimensiune astfel încât matricile care sunt mai mari să fie multiplicate mai eficient cu algoritmul lui Strassen decât modul „tradițional”. Cu toate acestea, afirmația asimptotică nu implică faptul că algoritmul lui Strassen este întotdeauna mai rapid chiar și pentru matricile mici și, în practică, acest lucru nu este de fapt cazul: Pentru matricile mici, costul adăugărilor suplimentare ale blocurilor de matrice depășește economiile în numărul de multiplicări. Există, de asemenea, alți factori care nu sunt surprinși de analiza de mai sus, cum ar fi diferența de cost pe hardware-ul actual între încărcarea datelor din memorie pe procesoare vs. costul efectuării operațiunilor pe aceste date. Ca o consecință a acestor tipuri de considerații, algoritmul lui Strassen este de obicei utilizat numai pe matrici „mari”. Acest tip de efect este chiar mai pronunțat cu algoritmi alternativi, cum ar fi cel de la Coppersmith și Winograd : Deși asimptotic chiar mai rapid, punctul de încrucișare este atât de mare încât algoritmul nu este utilizat în general pe matricile pe care le întâlnim în practică. ${\ displaystyle O (8 ^ {\ log _ {2} n}) = O (N ^ {\ log _ {2} 8}) = O (N ^ {3})}$${\ displaystyle N _ {\ text {prag}}}$${\ displaystyle N _ {\ text {prag}}}$

Rang sau complexitate biliniară

Complexitatea biliniară sau rangul unei hărți biliniare este un concept important în complexitatea asimptotică a multiplicării matricei. Rangul unei hărți biliniare pe un câmp F este definit ca (oarecum un abuz de notație ) ${\ displaystyle \ phi: \ mathbf {A} \ times \ mathbf {B} \ rightarrow \ mathbf {C}}$

${\ displaystyle R (\ phi / \ mathbf {F}) = \ min \ left \ {r \ left | \ există f_ {i} \ in \ mathbf {A} ^ {*}, g_ {i} \ in \ mathbf {B} ^ {*}, w_ {i} \ in \ mathbf {C}, \ forall \ mathbf {a} \ in \ mathbf {A}, \ mathbf {b} \ in \ mathbf {B}, \ phi (\ mathbf {a}, \ mathbf {b}) = \ sum _ {i = 1} ^ {r} f_ {i} (\ mathbf {a}) g_ {i} (\ mathbf {b}) w_ {i} \ right. \ right \}}$

Cu alte cuvinte, rangul unei hărți biliniare este lungimea celui mai scurt calcul al său biliniar. Existența algoritmului lui Strassen arată că rangul multiplicării matricei nu este mai mare de șapte. Pentru a vedea acest lucru, să exprimăm acest algoritm (alături de algoritmul standard) ca un astfel de calcul biliniar. În cazul matricilor, spațiile duale A * și B * constau din hărți în câmpul F induse de un produs scalar cu două puncte , (adică în acest caz suma tuturor intrărilor unui produs Hadamard .) ${\ displaystyle 2 \ times 2}$

	Algoritm standard				Algoritmul Strassen
${\ displaystyle i}$	${\ displaystyle f_ {i} (\ mathbf {a})}$	${\ displaystyle g_ {i} (\ mathbf {b})}$	${\ displaystyle w_ {i}}$		${\ displaystyle f_ {i} (\ mathbf {a})}$	${\ displaystyle g_ {i} (\ mathbf {b})}$	${\ displaystyle w_ {i}}$
1	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}}}$
2	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & -1 \ end {bmatrix}}}$
3	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & -1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 1 \ end {bmatrix}}}$
4	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} -1 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 1 & 0 \ end {bmatrix}}}$
5	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} -1 & 1 \\ 0 & 0 \ end {bmatrix}}}$
6	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} -1 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 1 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}}$
7	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 0 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & 0 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}}$		${\ displaystyle {\ begin {bmatrix} 0 & 1 \\ 0 & -1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 1 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 1 & 0 \\ 0 & 0 \ end {bmatrix}}}$
8	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {a}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}: \ mathbf {b}}$	${\ displaystyle {\ begin {bmatrix} 0 & 0 \\ 0 & 1 \ end {bmatrix}}}$
	${\ displaystyle \ mathbf {a} \ mathbf {b} = \ sum _ {i = 1} ^ {8} f_ {i} (\ mathbf {a}) g_ {i} (\ mathbf {b}) w_ { i}}$				${\ displaystyle \ mathbf {a} \ mathbf {b} = \ sum _ {i = 1} ^ {7} f_ {i} (\ mathbf {a}) g_ {i} (\ mathbf {b}) w_ { i}}$

Se poate arăta că numărul total de înmulțiri elementare necesare pentru înmulțirea matricei este strâns asimptotic legat de rang , adică sau mai precis, deoarece constantele sunt cunoscute ,. O proprietate utilă a rangului este că este submultiplicativă pentru produsele tensorale , iar acest lucru permite să se arate că multiplicarea matricei poate fi realizată cu cel mult multiplicări elementare pentru oricare . (Acest produs tensorial de mai multe ori al hărții de multiplicare a matricei cu el însuși - a -a-a tensiune tensională - este realizat prin pasul recursiv din algoritmul prezentat.) ${\ displaystyle L}$${\ displaystyle R}$${\ displaystyle L = \ Theta (R)}$${\ displaystyle R / 2 \ leq L \ leq R}$${\ displaystyle 2 ^ {n} \ times 2 ^ {n} \ times 2 ^ {n}}$${\ displaystyle 7n}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle 2 \ times 2 \ times 2}$${\ displaystyle n}$

Comportamentul memoriei cache

Algoritmul lui Strassen este ignorat de cache . Analiza algoritmului său de comportament în cache a arătat că are loc

${\ displaystyle \ Theta \ left (1 + {\ frac {n ^ {2}} {b}} + {\ frac {n ^ {\ log _ {2} 7}} {b {\ sqrt {M}} }}\dreapta)}$

cache-ul eșuează în timpul execuției sale, presupunând un cache idealizat de dimensiune (adică cu linii de lungime ). ${\ displaystyle M}$${\ displaystyle M / b}$${\ displaystyle b}$

Considerații privind implementarea

Descrierea de mai sus afirmă că matricile sunt pătrate, iar dimensiunea este o putere de două și că ar trebui să se utilizeze căptușeala dacă este necesar. Această restricție permite împărțirea matricilor în jumătate, recursiv, până la atingerea limitei de multiplicare scalară. Restricția simplifică explicația și analiza complexității, dar nu este de fapt necesară; și de fapt, umplerea matricei așa cum este descris va crește timpul de calcul și poate elimina cu ușurință economiile de timp destul de restrânse obținute prin utilizarea metodei în primul rând.

O implementare bună va respecta următoarele:

• Nu este necesar sau de dorit să se utilizeze algoritmul Strassen până la limita scalarilor. Comparativ cu înmulțirea matricei convenționale, algoritmul adaugă o sarcină de lucru considerabilă în plus / scăderi; deci sub o anumită dimensiune, va fi mai bine să folosiți multiplicarea convențională. Astfel, de exemplu, nu trebuie să fie umplut cu , deoarece ar putea fi împărțit în matrice și multiplicarea convențională poate fi apoi utilizată la acel nivel.${\ displaystyle O (n ^ {2})}$${\ displaystyle 1600 \ times 1600}$${\ displaystyle 2048 \ times 2048}$${\ displaystyle 25 \ times 25}$
• Metoda poate fi aplicată într-adevăr matricilor pătrate de orice dimensiune. Dacă dimensiunea este uniformă, acestea sunt împărțite în jumătate așa cum este descris. Dacă dimensiunea este impar, zero umplere cu un rând și o coloană se aplică mai întâi. O astfel de umplutură poate fi aplicată din mers și leneș, iar rândurile și coloanele suplimentare aruncate pe măsură ce se formează rezultatul. De exemplu, să presupunem că matricile sunt . Pot fi împărțite astfel încât porțiunea stânga sus să fie și dreapta jos . Ori de câte ori operațiunile o necesită, dimensiunile lui sunt zero umplute până la primul. Rețineți, de exemplu, că produsul este utilizat numai în rândul inferior al ieșirii, deci trebuie să fie doar rânduri înalte; și, prin urmare, factorul din stânga folosit pentru a-l genera trebuie să fie doar rânduri înalte; în consecință, nu este necesară asocierea acestei sume la rânduri; este necesar doar pentru a pad pentru coloane pentru a se potrivi .${\ displaystyle 199 \ times 199}$${\ displaystyle 100 \ ori 100}$${\ displaystyle 99 \ times 99}$${\ displaystyle 99}$${\ displaystyle 100}$${\ displaystyle M_ {2}}$${\ displaystyle 99}$${\ displaystyle A_ {21} + A_ {22}}$${\ displaystyle 99}$${\ displaystyle 100}$${\ displaystyle A_ {22}}$${\ displaystyle 100}$${\ displaystyle A_ {21}}$

În plus, nu este nevoie ca matricele să fie pătrate. Matricele care nu sunt pătrate pot fi împărțite în jumătate folosind aceleași metode, rezultând matrici mai mici care nu sunt pătrate. Dacă matricile sunt suficient de non-pătrate, merită să reducem operația inițială la mai multe produse pătrate, folosind metode simple care sunt în esență , de exemplu: ${\ displaystyle O (n ^ {2})}$

• Un produs de dimensiuni poate fi realizat ca 20 de operații separate , aranjate pentru a forma rezultatul;${\ displaystyle [2N \ times N] \ ast [N \ times 10N]}$${\ displaystyle [N \ times N] \ ast [N \ times N]}$
• Un produs de dimensiuni poate fi realizat ca 10 operații separate , însumate pentru a forma rezultatul.${\ displaystyle [N \ times 10N] \ ast [10N \ times N]}$${\ displaystyle [N \ times N] \ ast [N \ times N]}$

Aceste tehnici vor face ca implementarea să fie mai complicată, în comparație cu simpla umplere la o pătrat de putere de doi; cu toate acestea, este o presupunere rezonabilă că oricine întreprinde o implementare a Strassen, mai degrabă decât o multiplicare convențională, va acorda o prioritate mai mare eficienței computaționale decât simplității implementării.

În practică, algoritmul lui Strassen poate fi implementat pentru a obține o performanță mai bună decât multiplicarea convențională chiar și pentru matricile mici, pentru matricile care nu sunt deloc pătrate și fără a necesita spațiu de lucru dincolo de tampoane care sunt deja necesare pentru o multiplicare convențională de înaltă performanță.

Vezi si

• Complexitatea computațională a operațiilor matematice
• Eliminarea Gauss – Iordania
• Algoritm Coppersmith – Winograd
• Reprezentarea matricei de ordinul Z
• Algoritm Karatsuba , pentru înmulțirea n- cifre întregi în loc de timp${\ displaystyle O (n ^ {\ log _ {2} 3})}$${\ displaystyle O (n ^ {2})}$
• Algoritmul Toom-Cook , o generalizare mai rapidă a algoritmului Karatsuba, care permite descompunerea recursivă de împărțire și cucerire în mai mult de 2 blocuri la un moment dat
• Algoritmul de multiplicare complex al lui Gauss multiplică două numere complexe folosind 3 multiplicări reale în loc de 4

Referințe

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein . Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN  0-262-03293-7 . Capitolul 28: Secțiunea 28.2: Algoritmul lui Strassen pentru multiplicarea matricii, pp. 735-741.

linkuri externe

• Weisstein, Eric W. „Formulele lui Strassen” . MathWorld .(include și formule pentru inversarea rapidă a matricei )
• Tyler J. Earnest, Algoritmul lui Strassen pe motorul de bandă largă celulară