Jak Strassen wymyślił swoją metodę mnożenia macierzy?

Słynny algorytm mnożenia macierzy Strassena jest dla nas prawdziwą ucztą, ponieważ zmniejsza złożoność czasu z tradycyjnego O (n ³ ) do O (n ^2.8 ).

Ale ze wszystkich zasobów, przez które przeszedłem, nawet książki Cormena i Stevena Skienny, wyraźnie nie mówią, jak Strassen o tym myślał.

Jakie jest uzasadnienie algorytmu mnożenia macierzy w Strassen? Czy to szczęśliwy wypadek, czy jest w tym coś głębszego?

Poza Strassenem nikt nie jest w stanie powiedzieć, w jaki sposób Strassen ma swój pomysł. Jednak mogę ci powiedzieć, jak sam mogłeś znaleźć tę formułę - pod warunkiem, że interesuje cię geometria algebraiczna i teoria reprezentacji. Daje to również narzędzia do pokazania, że ​​wzór Strassena jest tak dobry, jak to tylko możliwe, a dokładniej, że nie ma wzoru obliczającego iloczyn dwóch macierzy 2 × 2, który wykorzystuje mniej niż 7 mnożenia .

Ponieważ interesują Cię macierze, zakładam, że znasz podstawową algebrę liniową i będzie nieco rozmyta dla bardziej zaawansowanych szczegółów.

Najpierw niech E będzie zbiorem wszystkich map liniowych od płaszczyzny do płaszczyzny. Jest to w zasadzie zbiór wszystkich macierzy 2 × 2, ale zapominamy o konkretnym układzie współrzędnych - ponieważ gdyby istniał lepszy układ współrzędnych niż „domyślny”, moglibyśmy być zainteresowani jego wykorzystaniem do mnożenia macierzy. Oznaczamy również przez E † podwójną przestrzeń E i przez X = P (E⊗E † ⊗E †) przestrzeń rzutową powiązaną z iloczynem tensora E⊗E † ⊗E † .

Element X = P (E⊗E † ⊗E †) o specjalnej formie [c⊗α⊗β] można interpretować jako elementarną operację na macierzach, która w niektórych odpowiednich układach współrzędnych odczytuje współczynnik macierzy i współczynnik matrycy B i zapisuje iloczyn tych współczynników w niektórych macierzy C . Ogólny element X jest kombinacją tych elementarnych operacji, tak że produkt Õ dwóch macierzy, rozumianej jako mapa z P (E) x P (E) z P (E), to punkt X .

Zwykłą formułę iloczynu macierzowego i równanie Strassena można wyrazić jako kombinacje tych operacji liniowych, więc pozwól mi oznaczyć przez W₁ zbiór tych operacji elementarnych [c⊗α⊗β] i pozwól mi opisać geometrycznie ich kombinacje.

Niech W₂ być różnorodność siecznych z W₁ w X. Jest uzyskanych przez poświęcenie (zamknięcie) unia wszystkich linii przechodzących przez dwa (ogólne) punktów W₁ . Możemy myśleć o tym jak o zestawie wszystkich kombinacji dwóch operacji elemetarnych.

Niech W₃ być różnorodność siecznej samolotów z W₁ w X. Jest uzyskanych przez poświęcenie (zamknięcie) unia wszystkich płaszczyznach przechodzących przez trzy (ogólne) punktów W₁ . Możemy myśleć o tym jak o zestawie wszystkich kombinacji trzech operacji elemetarnych.

Podobnie definiujemy odmiany sieczne dla większych indeksów. Zauważ, że te odmiany rosną coraz bardziej, to znaczy W₁⊂W₂⊂W₃⊂ ⋯ Stąd klasyczna formuła produktu macierzowego pokazuje, że iloczyn macierzy jest punktem W₈ . Tak właściwie

PROPOSITION (Strassen) - Iloczyn macierzy π leży w W₇.

O ile mi wiadomo, Strassen nie przedstawił tego w ten sposób, jednak jest to geometryczny punkt widzenia na to pytanie. Ten punkt widzenia jest bardzo przydatny, ponieważ pozwala również udowodnić, że formuła Strassena jest najlepsza, to znaczy, że π nie leży w W₆ . Opracowane tutaj metody geometryczne można również zastosować do szerszego zakresu problemów.

Mam nadzieję, że złapałem twoją ciekawość. Możesz pójść dalej, czytając ten artykuł autorstwa Landsberga i Manivela:

http://arxiv.org/abs/math/0601097

¹ Nie naprawię tej literówki, ponieważ przeziębiłem się.

Właśnie mi powierzono zadanie do odrabiania lekcji i pomyślałem, że miałem fajne objawienie: algorytm Strassena poświęca „szerokość” swoich składników do podsumowania, aby użyć mniej operacji w zamian za „głębsze” elementy do podsumowania które nadal można wykorzystać do wyodrębnienia ostatecznej odpowiedzi. (To nie jest najlepszy sposób, aby to powiedzieć, ale trudno mi to wytłumaczyć).

Użyję przykładu pomnożenia razem dwóch liczb zespolonych, aby zilustrować równowagę „ operacji vs. składników ”:

Zauważ, że używamy 4 multiplikacji, które dają 4 składniki produktu :

Zauważ, że 2 ostateczne składniki, które chcemy: rzeczywista i urojona część liczby zespolonej, są w rzeczywistości równaniami liniowymi: są to sumy skalowanych produktów. Mamy tutaj do czynienia z dwiema operacjami: dodawaniem i mnożeniem.

Faktem jest, że nasze 4 komponenty produktu mogą reprezentować nasze 2 końcowe komponenty, jeśli po prostu dodamy lub odejmiemy nasze komponenty:

Ale nasze ostatnie 2 elementy mogą być reprezentowane jako sumy produktów. Oto, co wymyśliłem:

Jeśli widzisz, w rzeczywistości potrzebujemy tylko 3 różnych składników produktu, aby nasze dwa ostatnie:

Ale poczekaj! Każda z wielkich liter jest sama w sobie produktem! Ale haczyk polega na tym, że wiemy, że możemy wygenerować (A + B + C + D) z (a + b) (c + d), co jest tylko 1 pomnożeniem.

Ostatecznie nasz algorytm jest zoptymalizowany pod kątem korzystania z mniejszych, ale „grubszych” komponentów, gdzie wymieniamy liczbę mnożeń na bardziej sumującą operację.

Częścią tego, co to umożliwia, jest właściwość dystrybucyjna, która umożliwia równoważność A (B + C) z (AB + AC). Zauważ, jak pierwszy można obliczyć za pomocą 1 operacji dodawania i 1 mnożenia, podczas gdy drugi wymaga 2 mnożeń i 1 sumy.

Algorytm Strassena jest rozszerzeniem optymalizacji, którą zastosowaliśmy do produktów liczb zespolonych, z tym wyjątkiem, że istnieje więcej terminów dotyczących produktów docelowych i możliwe więcej składników produktu, których możemy użyć, aby uzyskać te warunki. W przypadku macierzy 2x2 algorytm Strassena przekształca algorytm wymagający 8 multiplikacji w taki, który wymaga 7 multiplikacji, i wykorzystuje właściwość dystrybucyjną do „scalenia” dwóch multiplikacji w jedną operację, a zamiast tego usuwa nowy węzeł „grubszy” w celu wyodrębnienia jednego termin produktu lub inny, itp.

Dobry przykład: aby uzyskać (-1) i (2) i (5), możesz myśleć o tym jak o (-1), (2), (5) lub możesz o tym myśleć jako (2-3 ), (2), (2 + 3). Druga operacja używa jednak mniej wyraźnych liczb. Problem polega na tym, że liczba różnych liczb jest równoważna liczbie składników produktu, które należy obliczyć w celu pomnożenia macierzy. Po prostu optymalizujemy to w celu znalezienia pewnego widoku na podstawowe operacje, które wykorzystują wyniki izomorficzne przy użyciu innej odmiany w obrębie właściwości dystrybucyjnej.

Być może można to w jakiś sposób powiązać z topologią? To tylko sposób na zrozumienie tego przez mojego laika.

Edycja: Oto zdjęcie moich notatek, które narysowałem w trakcie wyjaśniania liczby złożonej: