Mnożenie nie tylko macierzy

Tematem tego artykułu jest mnożenie macierzy, ale zaczniemy od problemu nieco prostszego - mnożenia wielomianów...

Mnożenie wielomianów za pomocą tego wzoru wymaga rzędu $n2$ operacji. Okazuje się jednak, że można to zrobić szybciej. Jako pierwszy zauważył to Anatolij Karatsuba już w 1960 roku. Algorytm Karatsuby opiera się na następującym spostrzeżeniu. Rozważmy iloczyn wielomianów szczególnie prostej postaci:

n n 2n n (anx + a0)(bnx + b0) = anbnx + (anb0 + bna0)x + a0b0.

Wydaje się, że do obliczenia współczynników wyniku potrzebne są cztery mnożenia, ale wystarczą trzy, gdyż

anb0 + bna0 = (a0 + an)(b0 + bn) −a0b0 − anbn.

W ogólnym przypadku, aby pomnożyć dwa wielomiany $A,$ stopnia $|2n− 1,$ zapisujemy $|A$ następująco:

A(x)

i analogicznie $|B,$ a następnie korzystamy z wyprowadzonej właśnie tożsamości. Sprowadzamy w ten sposób jedno mnożenie wielomianów stopnia $|2n −1$ do trzech mnożeń oraz dwóch odejmowań wielomianów stopnia $|n −1.$ Proces ten można kontynuować rekurencyjnie. Liczbę operacji arytmetycznych, wykonywanych przez uzyskany w ten sposób algorytm, opisuje równanie $|T(2n − 1) = 3T (n− 1)+ O(n),$ którego rozwiązaniem jest $|T(n − 1) = O(n$ gdzie $|log23 ≈1,585.$ Jeśli początkowe stopnie nie są postaci $|2k− 1,$ należy je sztucznie zwiększyć, nie zmienia to rzędu liczby operacji.

Istnieją też inne efektywne algorytmy mnożenia wielomianów. Najszybszy z nich korzysta z szybkiej transformaty Fouriera i wymaga $|O(n$ operacji arytmetycznych. Warto zwrócić uwagę, że algorytmów tych można używać także do mnożenia liczb, wstawiając za współczynniki wielomianów cyfry liczb, które chcemy pomnożyć. Poprawność tej procedury łatwo uzasadnić - wystarczy podstawić za $|x$ bazę systemu, w którym liczymy, np. $x = 10.$ Zarówno algorytm Karatsuby, jak i inne szybkie algorytmy mnożenia liczb/wielomianów są używane w praktyce. Wiele bibliotek implementuje kilka różnych algorytmów i wybiera właściwy w zależności od rozmiaru mnożonych liczb.

Przejdźmy teraz do głównego tematu tego artykułu, czyli mnożenia macierzy. Niech $|A$ i $B |$ będą macierzami $n × n,A$ Iloczynem $|A$ i $B |$ jest macierz $C$ gdzie $c = Pn a b . i, j k 1 i,k k, j$ Jak łatwo sprawdzić, mnożenie macierzy za pomocą tej definicji wymaga rzędu $|n3$ operacji. W 1969 roku Strassen zadziwił świat naukowy odkryciem algorytmu, który mnoży macierze za pomocą $O(nlog2$ operacji, gdzie $log 7 ≈ 2,81. 2$ Algorytm ten opiera się na pomyśle podobnym do algorytmu Karatsuby. Strassen znalazł mianowicie metodę mnożenia dwóch macierzy $2 ×2$ za pomocą $7$ mnożeń zamiast $8,$ które wykonuje algorytm naiwny. Aby móc zastosować algorytm Strassena rekurencyjnie, wystarczy zauważyć, że jeśli każdą z macierzy $|A,$ oraz $|C$ podzielimy na cztery identycznych rozmiarów kwadratowe bloki, to zachodzi:

(C1,1C1,2 ) = (A1,1B1,1 A1,1B1,2 ) . C2,1C2,2 A2,1B1,1 A2,1B1,2

Oznacza to, że można takie macierze blokowe mnożyć tak, jakby bloki były liczbami. W połączeniu ze sztuczką Strassena pozwala to zredukować mnożenie macierzy $| (2n) × (2n)$ do $| 7$ mnożeń macierzy $| n× n$ i pewnej, zupełnie nieistotnej, liczby dodawań takich macierzy. Złożoność uzyskanego w efekcie algorytmu rekurencyjnego opisuje równanie $|T(2n) = 7T (n)+ O(n2),$ którego rozwiązaniem jest wspomniana wcześniej złożoność $T(n) = O(n$

Po odkryciu Strassena sądzono, że znalezienie algorytmu o złożoności $|O(n$ lub podobnej jest tylko kwestią czasu. Stało się jednak inaczej. Przez kolejnych dwadzieścia lat rozwinięto niezwykle wyrafinowaną metodologię konstrukcji algorytmów mnożenia macierzy, wyrażoną w języku algebry tensorowej. W ramach tej teorii zaproponowano wiele algorytmów mnożenia macierzy, najszybszym z nich jest opublikowany w roku 1980 algorytm Coppersmitha i Winograda o złożoności $|O(n2,38).$ Od tamtego czasu powstały nowe, dużo bardziej eleganckie teorie, m.in. interpretacja znanych algorytmów w języku działań grup. Parametry algorytmu Coppersmitha i Winograda zostały też zoptymalizowane, w efekcie uzyskano złożoność $|O(n2,37).$ Pytanie o algorytm o złożoności niemal kwadratowej pozostaje nadal jednym z najbardziej fundamentalnych otwartych problemów algorytmiki.

Nie jest to jednak jedyny otwarty problem związany z mnożeniem macierzy. Mnożenie macierzy jest niezwykle często wykorzystywane w praktyce, choćby w implementacji warstw gęstych w tak ostatnio popularnych sieciach neuronowych. Pomimo to żadna z popularnych zoptymalizowanych implementacji nie korzysta z omawianych tu algorytmów. Powody ku temu są dwa. W przypadku najszybszych asymptotycznie algorytmów stała ukryta w notacji dużego $O |$ ma monstrualne rozmiary, przez co są one bezużyteczne w praktyce. Z kolei w przypadku wolniejszych asymptotycznie algorytmów, np. algorytmu Strassena, rekurencyjna struktura utrudnia efektywne zarządzanie pamięcią podręczną procesora (cache), które jest kluczowym elementem efektywnych implementacji. Czy istnieją naprawdę szybkie algorytmy mnożenia macierzy?