De la Wikipedia, enciclopedia liberă.
În matematică și mai ales în algebră liniară , prin algoritmul lui Strassen înțelegem un algoritm (datorat matematicianului german Volker Strassen ) care vizează calcularea produsului a două matrice. Este decisiv mai puțin intuitiv decât procedura bazată pe formula pentru definirea produsului între matrice (pe care o vom numi procedura standard), dar are o ordine de complexitate mai mică.
Istorie
Volker Strassen a propus algoritmul care îi poartă numele în 1969 . Este un algoritm care în comparație cu standardul este puțin mai rapid, dar este semnificativ mai complex de implementat și necesită mai multă memorie. Toate acestea înseamnă că este rar folosit în aplicații de interes practic. Cu toate acestea, se întâmplă ca Strassen să fi fost primul care a subliniat că algoritmul Gauss nu este o procedură optimă, iar scrierile sale despre acest subiect au început căutarea unor algoritmi și mai rapizi (cum ar fi algoritmul Coppersmith - Winograd ) și, în general, căutarea algoritmi care se îndepărtează de cei mai intuitivi.
Algoritm
Fie A și B două matrice pătrate cu același aspect pe un câmp K. Vrem să calculăm matricea produsului C
- {\ displaystyle \ mathbf {C}: = \ mathbf {A} \ mathbf {B} \ qquad \ mathbf {A}, \ mathbf {B}, \ mathbf {C} \ in \ mathbb {K} ^ {2 ^ {n} \ ori 2 ^ {n}}}
Dacă matricile A și B nu au un aspect al formei 2 n × 2 n umplem rândurile și coloanele care lipsesc atunci când acest aspect este atins cu zerouri.
Descompunem A , B și C în submatrixe cu extensii înjumătățite
- {\ displaystyle \ mathbf {A} =: {\ begin {pmatrix} \ mathbf {A} _ {1,1} & \ mathbf {A} _ {1,2} \\\ mathbf {A} _ {2, 1} & \ mathbf {A} _ {2,2} \ end {pmatrix}} {\ mbox {,}} \ mathbf {B} =: {\ begin {pmatrix} \ mathbf {B} _ {1,1 } & \ mathbf {B} _ {1,2} \\\ mathbf {B} _ {2,1} & \ mathbf {B} _ {2,2} \ end {pmatrix}} {\ mbox {,} } \ mathbf {C} =: {\ begin {pmatrix} \ mathbf {C} _ {1,1} & \ mathbf {C} _ {1,2} \\\ mathbf {C} _ {2,1} & \ mathbf {C} _ {2,2} \ end {pmatrix}}}
cu
- {\ displaystyle \ mathbf {A} _ {i, j}, \ mathbf {B} _ {i, j}, \ mathbf {C} _ {i, j} \ in \ mathbb {K} ^ {2 ^ { n-1} \ times 2 ^ {n-1}}}
.
Pentru submatrixuri se găsește
- {\ displaystyle \ mathbf {C} _ {1,1} = \ mathbf {A} _ {1,1} \ mathbf {B} _ {1,1} + \ mathbf {A} _ {1,2} \ mathbf {B} _ {2,1}}
- {\ displaystyle \ mathbf {C} _ {1,2} = \ mathbf {A} _ {1,1} \ mathbf {B} _ {1,2} + \ mathbf {A} _ {1,2} \ mathbf {B} _ {2,2}}
- {\ displaystyle \ mathbf {C} _ {2,1} = \ mathbf {A} _ {2,1} \ mathbf {B} _ {1,1} + \ mathbf {A} _ {2,2} \ mathbf {B} _ {2,1}}
- {\ displaystyle \ mathbf {C} _ {2,2} = \ mathbf {A} _ {2,1} \ mathbf {B} _ {1,2} + \ mathbf {A} _ {2,2} \ mathbf {B} _ {2,2}}
Cu această construcție nu am redus numărul de înmulțiri. Mai avem nevoie de 8 înmulțiri pentru a calcula matricile C i, j , avem nevoie de același număr de înmulțiri dacă folosim procedura standard de înmulțire.
Inovația constă în definirea unor noi matrice
- {\ displaystyle \ mathbf {M} _ {1}: = (\ mathbf {A} _ {1,1} + \ mathbf {A} _ {2,2}) (\ mathbf {B} _ {1,1 } + \ mathbf {B} _ {2,2})}
- {\ displaystyle \ mathbf {M} _ {2}: = (\ mathbf {A} _ {2,1} + \ mathbf {A} _ {2,2}) \ mathbf {B} _ {1,1} }
- {\ displaystyle \ mathbf {M} _ {3}: = \ mathbf {A} _ {1,1} (\ mathbf {B} _ {1,2} - \ mathbf {B} _ {2,2}) }
- {\ displaystyle \ mathbf {M} _ {4}: = \ mathbf {A} _ {2,2} (\ mathbf {B} _ {2,1} - \ mathbf {B} _ {1,1}) }
- {\ displaystyle \ mathbf {M} _ {5}: = (\ mathbf {A} _ {1,1} + \ mathbf {A} _ {1,2}) \ mathbf {B} _ {2,2} }
- {\ displaystyle \ mathbf {M} _ {6}: = (\ mathbf {A} _ {2,1} - \ mathbf {A} _ {1,1}) (\ mathbf {B} _ {1,1 } + \ mathbf {B} _ {1,2})}
- {\ displaystyle \ mathbf {M} _ {7}: = (\ mathbf {A} _ {1,2} - \ mathbf {A} _ {2,2}) (\ mathbf {B} _ {2,1 } + \ mathbf {B} _ {2,2})}
și în utilizarea acestora pentru a exprima C i, j în termeni de M k . Conform definiției lui M k putem elimina un produs de matrice și putem reduce numărul de înmulțiri la 7 (o înmulțire pentru fiecare M k ) și să exprimăm C i, j ca
- {\ displaystyle \ mathbf {C} _ {1,1} = \ mathbf {M} _ {1} + \ mathbf {M} _ {4} - \ mathbf {M} _ {5} + \ mathbf {M} _ {7}}
- {\ displaystyle \ mathbf {C} _ {1,2} = \ mathbf {M} _ {3} + \ mathbf {M} _ {5}}
- {\ displaystyle \ mathbf {C} _ {2,1} = \ mathbf {M} _ {2} + \ mathbf {M} _ {4}}
- {\ displaystyle \ mathbf {C} _ {2,2} = \ mathbf {M} _ {1} - \ mathbf {M} _ {2} + \ mathbf {M} _ {3} + \ mathbf {M} _ {6}}
Puteți itera acest proces de reducere la jumătate a dimensiunile n- ori până când submatrixes sunt reduse la simple numere.
Complexitatea computațională
Produsul a două n × n matrici realizate prin simpla aplicare a definiției necesită
- {\ displaystyle n ^ {3} = n ^ {\ log _ {2} 8}}
multiplicarea elementelor din câmpul K. Adaosurile pot fi neglijate deoarece apar mult mai repede decât înmulțirile.
Cu algoritmul lui Strassen, numărul de multiplicări este redus la
- {\ displaystyle n ^ {\ log _ {2} 7} \ approx n ^ {2.8074}}
.
Bibliografie
linkuri externe
