Info & MatematicăMatematică şi informatică pe pâine…

8 Inmultirea matricilor

Pentru matricile A si B de n  n
elemente, dorim sa obtinem matricea produs C = AB. Algoritmul
clasic provine direct din definitia inmultirii a doua matrici si necesita n³
inmultiri si (n-1)n² adunari
scalare. Timpul necesar pentru calcularea matricii C este deci in Q(n³).
Problema pe care ne-o punem este sa gasim un algoritm de inmultire matriciala
al carui timp sa fie intr-un ordin mai mic decat n³. Pe de
alta parte, este clar ca W(n²)
este o limita inferioara pentru orice algoritm de inmultire matriciala, deoarece
trebuie in mod necesar sa parcurgem cele n² elemente ale lui
C.

Strategia divide et impera sugereaza un alt mod de calcul a matricii C.
Vom presupune in continuare ca n este o putere a lui doi. Partitionam
pe A si B in cate patru submatrici de n/2  n/2
elemente fiecare. Matricea produs C se poate calcula conform formulei
pentru produsul matricilor de 2  2 elemente:

_{src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_13.gif" v:shapes="_x0000_i1037">}

unde

_{src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_14.gif" v:shapes="_x0000_i1038">}

Pentru n = 2, inmultirile si adunarile din relatiile de mai
sus sunt scalare; pentru n > 2, aceste operatii sunt intre
matrici de n/2  n/2 elemente.
Operatia de adunare matriciala este cea clasica. In schimb, pentru fiecare inmultire
matriciala, aplicam recursiv aceste partitionari, pana cand ajungem la submatrici
de 2  2 elemente.

Pentru a obtine matricea C, este nevoie de opt inmultiri si patru adunari
de matrici de n/2  n/2 elemente.
Doua matrici de n/2  n/2
elemente se pot aduna intr-un timp in Q(n²).
Timpul total pentru algoritmul divide et impera rezultat este

t(n)  8t(n/2) + Q(n²)

Definim functia

_{src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_15.gif" v:shapes="_x0000_i1039">}

Din Proprietatea 5.2 rezulta ca f  Q(n³).
Procedand ca in Sectiunea 5.1.2, deducem ca t  Q( f ) = Q(n³),
ceea ce inseamna ca nu am castigat inca nimic fata de metoda clasica.

In timp ce inmultirea matricilor necesita un timp cubic, adunarea matricilor
necesita doar un timp patratic. Este, deci, de dorit ca in formulele pentru
calcularea submatricilor C sa folosim mai putine inmultiri, chiar daca
prin aceasta marim numarul de adunari. Este insa acest lucru si posibil? Raspunsul
este afirmativ. In 1969, Strassen a descoperit o metoda de calculare a submatricilor
C_ij, care utilizeaza 7 inmultiri si 18 adunari si scaderi.
Pentru inceput, se calculeaza sapte matrici de n/2  n/2
elemente:

_{src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_16.gif" v:shapes="_x0000_i1040">}

Este usor de verificat ca matricea produs C se obtine astfel:

_{src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_17.gif" v:shapes="_x0000_i1041">}

Timpul total pentru noul algoritm divide et
impera este

t(n)  7t(n/2) + Q(n²)

si in mod similar deducem ca t  Q(n^lg 7).
Deoarece lg 7 < 2,81, rezulta ca t  O(n^2,81).
Algoritmul lui Strassen este deci mai eficient decat algoritmul clasic de inmultire
matriciala.

Metoda lui Strassen nu este unica: s-a
demonstrat ca exista exact 36 de moduri diferite de calcul a submatricilor C_ij, fiecare din aceste metode utilizand 7 inmultiri.

Limita O(n^2,81) poate fi si mai mult redusa daca gasim
un algoritm de inmultire a matricilor de 2  2
elemente cu mai putin de sapte inmultiri. S-a demonstrat insa ca acest lucru
nu este posibil. O alta metoda este de a gasi algoritmi mai eficienti pentru
inmultirea matricilor de dimensiuni mai mari decat 2  2
si de a descompune recursiv pana la nivelul acestor submatrici. Datorita constantelor
multiplicative implicate, exceptand algoritmul lui Strassen, nici unul din acesti
algoritmi nu are o valoare practica semnificativa.

Pe calculator, s-a putut observa ca,
pentru n  40, algoritmul lui Strassen este mai eficient decat metoda
clasica. In schimb, algoritmul lui Strassen foloseste memorie suplimentara.

Poate ca este momentul sa ne intrebam de unde provine acest interes pentru
inmultirea matricilor. Importanta acestor algoritmi
[***] deriva din faptul ca operatii frecvente cu matrici (cum ar fi inversarea
sau calculul determinantului) se bazeaza pe inmultiri de matrici. Astfel, daca
notam cu f (n) timpul necesar pentru a inmulti doua matrici
de n  n elemente si cu g(n)
timpul necesar pentru a inversa o matrice nesingulara de n  n
elemente, se poate arata ca f  Q(g).

clear=all>

Pagini: 1 2 3 4 5 6 7 8 9 10