ALG#1

9.1. Programowanie typu „dziel-i-rządź’’ 231

9.1. Programowanie typu „dziel-i-rządź’’ 231

P = (AU+AV)(BU+B22)	* +, +
0 = (A2[+A21)Bn	+. *
R - Au(Bn-Bv)	* _
S = A22(B1X-BJ	* _
T = B22(An+Atl)	*, +
U = (A2rAu)(Bu+BJ
V = (Ar-Ar)(B2]+Bn)
mamy te cząstkowe wyniki, otrzymanie matrycy C może być dokonane rzez następujące podstawienia:
C„ = P + S- T+ V
(j, = R + T	+
C21 = O+S	+
c„ = r + R-o+u	+, +

Algorytm tej postaci wymaga 7 operacji * i dodatkowych 18 operacji + lub

Zauważmy, że algorytm Strassena przenosi w inteligentny sposób ciężar obliczeń z zawsze kosztownej operacji mnożenia'¹ na znacznie szybsze dodawanie lub odejmowanie.

Rozkład rekurencyjny w algorytmie V. Strassena jest następujący:

N

T(n) = TI ^—j + aN² eO(jV^2,81)

(o jest pewną stałą).

Bliższe badania praktyczne tego algorytmu wykazały, że realny zysk powyższej metody daje się zauważyć w przypadku mnożenia matryc dla N rzędu kilkadziesiąt, ale w przypadku naprawdę dużych A'(np. powy'żej 100) efektywność algorytmu ponownie zbliża się do swojego iteracyjnego „konkurenta”. Fenomen ten zależy m.in. od sposobu zarządzania pamięcią w danym środowisku sprzętowym. Jeśli mamy do czynienia z komputerem osobistym o dużym „prywatnym" zasobie pamięci, to działanie algorytmu będzie zbliżone do przewidywań teoretycznych. Jednak w przypadku systemów rozproszonych, w których program „widząc” ⁴ Zwłaszcza jeśli elementami macierzy są liczby „rzeczywiste” (typ double w C++).