Złożoność czasu mnożenia macierzy w MATLAB

Question

Czy ktoś wie, jakiego algorytmu używa MATLAB do multiplikacji macierzy i jaka jest złożoność czasu?

Answer 1

Dla kompletności - jak wspomniano w this thread, Matlab używa DGEMM (Dwuosobowy Ogólne Matrix Mnożenie) rutynowe z BLAS (podstawowy algebra liniowa podprogramu).

Należy zauważyć, że nie ma jednej implementacji BLAS - jest dostrojony do konkretnych architektur procesorów. Dlatego nie można mieć absolutnej pewności, który algorytm jest używany na komputerze, bez sprawdzania, która wersja BLAS jest w użyciu.

Specyfikacja BLAS określa wejścia i wyjścia każdego podprogramu i zapewnia akceptowalne granice błędów dla wyjścia każdej podprogramu. Implementacje mogą dowolnie używać dowolnego algorytmu, pod warunkiem, że będą zgodne ze specyfikacją.

przykład implementacja BLAS wykorzystuje block matrix multiplication algorithm w DGEMM który ma czas złożoność O (n^3) do mnożenia dwóch n x n macierzy. Sądzę, że rozsądne jest założenie, że większość wdrożeń BLAS będzie mniej więcej zgodna z implementacją referencyjną.

Zauważ, że nie korzysta z naiwnego algorytmu mnożenia macierzy

for i = 1:N 
    for j = 1:N 
     for k = 1:N 
      c(i,j) = c(i,j) + a(i,k) * b(k,j); 
     end 
    end 
end 

To dlatego, że zwykle, cała matryca nie zmieści się w local memory. Jeśli dane są ciągle przenoszone do pamięci lokalnej i z niej, algorytm zwalnia. Algorytm macierzy bloków dzieli operację na małe bloki, tak że każdy blok jest wystarczająco mały, aby zmieścił się w lokalnej pamięci, zmniejszając liczbę przesunięć do i z pamięci.

Istnieją asymptotycznie szybsze algorytm mnożenia macierzy, np Strassen algorithm lub Coppersmith-Winograd algorithm które mają nieco szybciej niż o (n^3). Jednak generalnie nie są one chronione pamięcią podręczną i ignorują lokalizację - co oznacza, że ​​dane muszą być nieustannie przemieszczane w pamięci, tak więc w przypadku większości nowoczesnych architektur ogólny algorytm jest w rzeczywistości wolniejszy niż zoptymalizowany algorytm mnożenia macierzy blokowej.

Wikipedia zauważa, że ​​algorytm Strassena może zapewniać przyspieszenia na pojedynczym rdzeniu procesora w przypadku macierzy o rozmiarach większych niż kilka tysięcy, jednak przyspieszenie może wynosić około 10% lub mniej, a twórcy BLAS prawdopodobnie nie uważają tego Warto w tym rzadkim przypadku (mówiąc, że this paper z 1996 r. twierdzi, że wzrost prędkości o około 10% w stosunku do DGEMM dla n powyżej około 200 - choć nie wiem, jak nieaktualny). Z kolei algorytm Coppersmith-Winograd "zapewnia przewagę tylko dla macierzy tak dużych, że nie mogą być przetwarzane przez nowoczesny sprzęt".

Więc odpowiedź brzmi, że Matlab używa naiwnego, ale wydajnego algorytmu świadomego pamięci podręcznej, aby uzyskać szybką, szybką mnożenie macierzy.

---

Zaktualizowałem tę odpowiedź, tworząc kilka filmów, które demonstrują lokalizację algorytmu mnożenia macierzy blokowej, w porównaniu do algorytmu naiwnego.

W każdym z tych filmów, jesteśmy wizualizacji mnożenia dwóch macierzy 8x8 i B utworzyć produkt C = x B. Żółty kolor wskazuje, który element w każdej z macierzy jest przetwarzany na każdym etapie algorytmu. Możesz zobaczyć, w jaki sposób mnożenie macierzy bloków działa tylko na małych blokach macierzy naraz i ponownie wielokrotnie korzysta z każdego z tych bloków, aby zminimalizować liczbę przypadków, w których dane muszą być przenoszone i usuwane z pamięci lokalnej. .

• Simple matrix multiplication
• Block matrix multiplication, block size = 2
• Block matrix multiplication, block size = 4