ALG#0

230

Rozdział 9. Zaawansowane techniki programowania

Koszt wyliczenia jednego elementu macierzy C, mając na uwadze ilość wykonywanych operacji mnożenia (przyjmijmy rozsądnie, że to one są tu ^najkosztowniejsze’'), jest równy oczywiście N. Ponieważ wszystkich elementów jest .V, to koszt całkowity wyniesie AT, czyli program należy do 0(N)\

Algorytm jest bardzo kosztowny, ale wydawało się to przez długi czas tak nieuniknione, że praktycznie wszyscy się z tym pogodzili. W roku 1968 Volker Strassen sprawił jednakże wszystkim sporą niespodziankę, wynajdując algorytm bazujący na idei „dziel-i-rządź”, który był lepszy niż wydawałoby się „nienaruszalne” 0(N)^S.

Oznaczmy elementy macierzy A. B i C' w sposób następujący:

A.	4/		X	V		c„	C12‘
		•			—
A.	a22		A	b21		_Qi	^C22,

Nie jest trudno wykazać, że prawdziwe są następujące równości:

61| — A_uB_n+A_nB_2i,

Cj₂ = A„B_I2+Ą₂B₂₂,

— /4,| 5| i+zł,,

C₂₂ = A_2iB_I2+A₂₂B₂₂.

Podejście polegające na podziale każdej z matryc A i B na 4 równe części (zakładając oczywiście, że W jest potęgą liczby 2...) i wykonanie mnożenia matryc mniejszego rzędu wydaje się bezpośrednim zastosowaniem techniki „dziel-i-rządź”. Ponieważ jednak podział nie oszczędza nam pracy (w dalszym ciągu jesteśmy zmuszeni do zrobienia dokładnie tego samego, co algorytm iteracyjny), to na pewno nie otrzymamy tu efektywniejszego algorytmu. Stwierdzenie to nie jest poparte obliczeniami. ale zapewniam, że jest prawdziwe.

Spójrzmy teraz jak V. Strassen zoptymalizował mnożenie macierzy. Zasadnicza idea jego metody polega na wprowadzeniu dodatkowych „zmiennych”, będących matrycami rzędu —: P, Q, R, S, T, U, V, służących do zapamiętania wy-

2

ników następujących obliczeń’:

’ Obok równań są zaznaczone operacje arytmetyczne wymagane do wyliczenia danej równości.