Algorytm Strassena

Algorytm Strassena to metoda stosowana do mnożenia macierzy, nazwana na cześć swojego wynalazcy, Volkera Strassena. W porównaniu do tradycyjnych metod, jest on szybszy i bardziej efektywny przy przetwarzaniu dużych macierzy, jednak dla bardzo dużych macierzy działa wolniej niż najszybsza znana obecnie metoda, czyli algorytm Coppersmitha-Winograda.

Algorytm został zaprezentowany w 1969 roku. Choć jego wydajność była tylko nieznacznie lepsza od klasycznej metody, jako pierwszy wskazał, że tradycyjne podejście do mnożenia macierzy nie jest optymalne. To odkrycie zainicjowało poszukiwania jeszcze bardziej efektywnych algorytmów, co doprowadziło do powstania algorytmu Coppersmitha-Winograda w 1987 roku.

Działanie algorytmu

Rozważmy dwie macierze kwadratowe A oraz B, które są elementami pierścienia R. Celem jest obliczenie macierzy C, która spełnia równanie:

C = A * B, gdzie A, B, C należą do R^{2ⁿ × 2ⁿ}.

W przypadku, gdy macierze A i B nie mają rozmiaru 2ⁿ × 2ⁿ, uzupełniamy brakujące kolumny i wiersze zerami. Następnie dzielimy macierze A, B i C na mniejsze macierze o równych wymiarach:

A = [A_1,1, A_1,2; A_2,1, A_2,2]
B = [B_1,1, B_1,2; B_2,1, B_2,2]
C = [C_1,1, C_1,2; C_2,1, C_2,2]

gdzie:

A_i,j, B_i,j, C_i,j ∈ R^{2ⁿ⁻¹ × 2ⁿ⁻¹}.

Przykładowo, macierz C_1,1 oblicza się jako:

C_1,1 = A_1,1 * B_1,1 + A_1,2 * B_2,1.

W ten sposób, pomimo że używamy osiem mnożeń, nie redukujemy ich liczby, co daje nam wyniki porównywalne z tymi z klasycznego mnożenia macierzy.

Definiujemy nowe macierze w następujący sposób:

M₁ := (A_1,1 + A_2,2)(B_1,1 + B_2,2)
M₂ := (A_2,1 + A_2,2)B_1,1
M₃ := A_1,1(B_1,2 − B_2,2)
M₄ := A_2,2(B_2,1 − B_1,1)
M₅ := (A_1,1 + A_1,2)B_2,2
M₆ := (A_2,1 − A_1,1)(B_1,1 + B_1,2)
M₇ := (A_1,2 − A_2,2)(B_2,1 + B_2,2)

Te macierze są następnie używane do obliczenia macierzy C_i,j w oparciu o M_k, co pozwala wyeliminować jedno z mnożeń w algorytmie:

C_1,1 = M₁ + M₄ − M₅ + M₇
C_1,2 = M₃ + M₅
C_2,1 = M₂ + M₄
C_2,2 = M₁ − M₂ + M₃ + M₆

Cały proces podziału powtarzamy n razy, aż do momentu, gdy podmacierze staną się liczbami (elementami pierścienia R).

W praktyce algorytm Strassena przekształca standardową metodę mnożenia macierzy do mniejszych podmacierzy, dla których jego zastosowanie jest bardziej efektywne. Efektywność algorytmu Strassena może się różnić w zależności od implementacji oraz używanego sprzętu.

Złożoność obliczeniowa

Standardowa metoda mnożenia macierzy charakteryzuje się złożonością obliczeniową rzędu θ(n³), ponieważ wymaga 8 rekurencyjnych operacji mnożenia. W przypadku algorytmu Strassena, dzięki zastosowaniu innego podejścia, potrzebne są jedynie 7 rekurencyjnych mnożeń oraz θ(n²) operacji dodawania lub odejmowania. W rezultacie osiągamy złożoność obliczeniową θ(n^{lg 7}), co w przybliżeniu daje θ(n^2,81).

Implementacja algorytmu w języku C

W tej sekcji można by było przedstawić przykładowy kod źródłowy implementujący algorytm Strassena w języku C.

Bibliografia

Volker Strassen, Gaussian Elimination is not Optimal, Numer. Math. 13, s. 354–356, 1969.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Wprowadzenie do algorytmów, wyd. siódme, Wydawnictwa Naukowo-Techniczne, s. 751–758, Warszawa 2005.