Który algorytm jest skuteczny dla mnożenia macierzy 4×4 macierzy transformacji afinicznych

Wikipedia podaje cztery algorytmy dla mnożenia macierzy przez dwie macierze nxn .

Klasyczny algorytm, który napisałby programista to O (n ³ ) i jest wymieniony jako „Mnożenie macierzy w Schoolbook”. Tak. O (n ³ ) to trochę strzał w dziesiątkę. Spójrzmy na następny najlepszy.

Algorytim Strassena to O (n ^2.807 ). Ten by działał – ma pewne ograniczenia (na przykład rozmiar jest potęgą dwóch) i ma zastrzeżenie w opisie:

W porównaniu do konwencjonalnego mnożenia macierzy, algorytm dodaje znaczną ilość pracy O (n ² ) do dodawania / odejmowania; więc poniżej pewnego rozmiaru lepiej będzie użyć konwencjonalnego mnożenia.

Dla tych, którzy są zainteresowani tym algorytmem i jego początkami, spójrz na Jak Strassen wymyślił swoją metodę mnożenia macierzy? może być dobrą lekturą. Daje wskazówkę na temat złożoności tego początkowego obciążenia O (n ² ), które jest dodawane i dlaczego byłoby to droższe niż zwykłe wykonywanie klasycznego mnożenia.

Więc naprawdę jest O (n ² + n ^2.807 ) z tym bitem o niższym wykładniku n , które jest ignorowane podczas pisania dużego O. Wygląda na to, że jeśli pracują na ładnej matrycy 2048×2048, to może się przydać. W przypadku macierzy 4×4 prawdopodobnie będzie wolniej, ponieważ ten narzut pochłania przez cały czas.

A potem jest Coppersmith – Winograd algorytm , który jest O (n ^2.373 ) z kilkoma poprawkami. Zawiera również zastrzeżenie:

Algorytm Coppersmith-Winograd jest często używany jako element składowy innych algorytmów do udowodnienia teoretycznych granic czasowych. Jednak w przeciwieństwie do algorytmu Strassena nie jest używany w praktyce, ponieważ zapewnia przewagę tylko macierzy tak dużych, że nie mogą być przetwarzane przez nowoczesny sprzęt.

Tak więc jest lepiej, gdy pracujesz na bardzo dużych matrycach, ale znowu nie jest przydatny dla macierzy 4×4.

Ponownie znajduje to odzwierciedlenie na stronie Wikipedii w Mnożenie macierzy: algorytmy sub-sześcienne , które wyjaśniają, dlaczego rzeczy działają szybciej:

Istnieją algorytmy, które pr mają lepsze czasy pracy niż te proste. Pierwszym odkrytym był algorytm Strassena, opracowany przez Volkera Strassena w 1969 roku i często określany jako „szybkie mnożenie macierzy”. Opiera się on na sposobie mnożenia dwóch macierzy 2 × 2, który wymaga tylko 7 mnożeń (zamiast zwykłe 8), kosztem kilku dodatkowych operacji dodawania i odejmowania. Zastosowanie tego rekurencyjnego daje algorytm z multiplikatywnym kosztem O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Algorytm Strassena jest bardziej złożony, a stabilność numeryczna jest mniejsza w porównaniu z algorytmem naiwnym, ale jest szybszy w przypadkach, gdy n> 100 i pojawia się w kilku bibliotekach, takich jak BLAS.

I to już sedno tego, dlaczego algorytmy są szybsze – kompromis pewna stabilność numeryczna i dodatkowe ustawienia. Ta dodatkowa konfiguracja macierzy 4×4 to znacznie więcej niż koszt wykonania większego mnożenia.

A teraz, aby odpowiedzieć na twoje pytanie:

Ale czy są jakieś algorytmy, które są szczególnie wydajne dla tak małych macierzy?

Nie, nie ma algorytmów zoptymalizowanych pod kątem mnożenia macierzy 4×4, ponieważ O (n ³ ) działa całkiem rozsądnie dopóki nie odkryjesz, że jesteś skłonny przyjąć duży cios za głowę. W twojej konkretnej sytuacji może być pewien narzut, który możesz ponieść, wiedząc wcześniej o konkretnych rzeczach o swoich macierzach (np. Ile niektórych danych zostanie ponownie wykorzystanych), ale naprawdę najłatwiejszą rzeczą do zrobienia jest napisanie dobrego kodu dla O (n ³ ), pozwól kompilatorowi zająć się tym i sprofiluj go później, aby sprawdzić, czy faktycznie kod jest wolnym miejscem w mnożeniu macierzy.

Powiązane z Math.SE: Minimalna liczba mnożeń wymagana do odwrócenia macierzy 4×4

Często proste algorytmy są najszybsze w przypadku bardzo małych zbiorów, ponieważ bardziej złożone algorytmy zwykle używają transformacji, które powodują dodatkowe obciążenie. Myślę, że najlepszym rozwiązaniem nie jest wydajniejszy algorytm (myślę, że większość bibliotek używa prostych metod), ale bardziej wydajna implementacja, na przykład wykorzystująca rozszerzenia SIMD (zakładając kod x86 lub amd64) lub napisana ręcznie w asemblerze . Również układ pamięci powinien być dobrze przemyślany. Powinieneś być w stanie znaleźć wystarczające zasoby na ten temat.

W przypadku mnożenia mat / mat 4×4 ulepszenia algorytmów są często niedostępne . Podstawowy algorytm złożoności czasu sześciennego zwykle radzi sobie całkiem nieźle, a cokolwiek bardziej wyszukanego niż to, z większym prawdopodobieństwem degraduje niż poprawia czasy. Ogólnie rzecz biorąc, fantazyjne algorytmy są źle dopasowane, jeśli nie ma współczynnika skalowalności ta (np. Próba szybkiego sortowania tablicy, która zawsze ma 6 elementów, w przeciwieństwie do prostego wstawiania lub sortowania bąbelkowego). rzeczy takie jak transpozycja macierzy w tym miejscu w celu poprawy lokalizacji odniesienia również w rzeczywistości nie pomagają w zlokalizowaniu odniesienia, gdy cała macierz może zmieścić się w jednej lub dwóch liniach pamięci podręcznej. W tego rodzaju miniaturowej skali, jeśli wykonujesz mnożenie maty / maty 4×4 masowo, ulepszenia będą generalnie pochodzić z optymalizacji instrukcji i pamięci na poziomie mikro, takich jak prawidłowe wyrównanie linii pamięci podręcznej.

Komentarze

• Świetna odpowiedź! ' nigdy nie słyszałem o akronimie SoA (przynajmniej w języku niderlandzkim jest to akronim dla ' seksueel overdraagbare aandoening ' co oznacza ' chorobę przenoszoną drogą płciową ' … ale to ' mam nadzieję, że nie to, co masz na myśli). Technika wydaje się jasna, ' jestem nawet bardzo zaskoczony, że istnieje na nią nazwa. Co oznacza SoA?
• @Ruben Structure of Arrays w przeciwieństwie do Arrays of Structures. SoAs mogą być również PITA – najlepiej zachowane na najbardziej krytyczne ścieżki. Tutaj ' to fajny mały link, który znalazłem na ten temat: stackoverflow.com/questions/17924705/…
• Możesz wspomnieć o C ++ 11 / C11 alignas .

Jeśli wiesz na pewno, że wystarczy pomnożyć 4×4 macierzy, to w ogóle nie musisz się martwić o ogólny algorytm. Wystarczy wziąć dwa wskaźniki i użyć tego:

(Zdecydowanie polecam przetłumaczenie tego w sposób zautomatyzowany).

W takim przypadku kompilator optymalnie ustawiony, aby zoptymalizować ten kod (aby ponownie wykorzystać sumy częściowe, zmienić kolejność matematyki itp.), ponieważ może zobaczyć wszystko, nie ma pętli dynamicznych ani przepływu sterowania.

Trudno sobie wyobrazić, że można to pokonać bez używając elementów wewnętrznych.

Nie możesz bezpośrednio porównywać złożoności asymptotycznej, jeśli zdefiniujesz n inaczej. Jesteś przyzwyczajony do porównywania złożoności algorytmów na płaskich strukturach danych, takich jak listy, gdzie n jest definiowane jako całkowita liczba elementów w listy, ale algorytmy macierzowe definiują n jako długość tylko jednego boku .

Zgodnie z tą definicją n, coś tak prostego, jak przyjrzenie się każdemu elementowi raz w celu wydrukowania go, co normalnie myślisz jako O (n), to O (n ² ) . Jeśli zdefiniujesz n jako całkowitą liczbę elementów w macierzy, tj. N = 16 dla macierzy 4×4, to naiwne mnożenie macierzy wynosi tylko O (n ^1,5 ), co jest całkiem niezłe.

Najlepiej jest skorzystać z paralelizmu, używając instrukcji SIMD lub GPU, zamiast próbować ulepszać algorytm w oparciu o błędne przekonanie, że O (n ³ ) jest tak źle, jak byłoby, gdyby n zostały zdefiniowane w porównaniu z płaską strukturą danych.