Jak udowodnić, że mnożenia macierzy dwóch macierzy 2x2 nie można wykonać w mniej niż 7 multiplikacjach?

W mnożeniu macierzy Strassena stwierdzamy jeden dziwny (przynajmniej dla mnie) fakt, że mnożenie macierzy dwóch 2 x 2 wymaga mnożenia 7.

Pytanie: Jak udowodnić, że niemożliwe jest pomnożenie dwóch macierzy 2 x 2 w 6 pomnożeniach?

Należy pamiętać, że macierze są ponad liczbami całkowitymi.

algorithms complexity-theory lower-bounds

— Złożoność
źródło

Istnieją inne algorytmy mnożenia macierzy, które mogą być szybsze. Ten artykuł internetowy z klasy Stanford CME 323 zawiera szczegółowe informacje na temat algorytmu Strassena, mnożenia macierzy: algorytmu Strassena . Istnieje temat Wikipedii, algorytm Strassena, który zawiera szczegółowe informacje i zawiera linki do dodatkowych informacji.

— Richard Chambers

@RichardChambers Zauważ, że algorytm Strassena ma multiplikacji. Wydaje mi się prawdopodobne, że ta dolna granica jest prawdziwa.

7

$7$

— Stella Biderman

Zgodnie z brzmieniem to pytanie jest błędne. Istnieje wiele macierzy, które można pomnożyć przez mnożenia. Chcesz zapytać o dowód, że w najgorszym przypadku potrzeba 7 aka, istnieje matryca wymagająca 7

6

$6$

— Stella Biderman

@StellaBiderman tak Widziałem, że Strassen ma 7 multiplikacji. Nie patrzyłem na drugi, szybszy i algorytmy o mniejszej złożoności. Z tego, co mogę powiedzieć, używają tego samego podejścia podmacierzy, co Strassen, ale nie jestem pewien. Właśnie dodałem dodatkowe informacje o Strassen.

— Richard Chambers

Wydaje się, że czegoś brakuje w twoim pytaniu. Mogę z łatwością podać algorytm, który może pomnożyć przynajmniej niektóre macierze z 0 mnożeniami. Prawdopodobnie istnieje ograniczenie, o którym nie wspominasz.

— Jörg W Mittag

Odpowiedzi:

Jest to klasyczny wynik Winogradu: Mnożenie macierzy 2x2 .

Strassen wykazał, że wykładnik mnożenia macierzy jest taki sam, jak wykładnik stopnia tensora tensorów mnożenia macierzy: algebraiczna złożoność mnożenia macierzy wynosi i ranga tensora (tensor mnożenia macierzy odpowiadający mnożeniu dwóch macierzy) to . Algorytm Strassena używa łatwego kierunku, aby wydedukować z górnej granicy . $n\times n$ $O(n^\alpha)$ $\langle n,n,n \rangle$ $n\times n$ $O(n^\alpha)$ $O(n^{\log_27})$ $R(\langle 2,2,2 \rangle) \leq 7$

Wynik Winograda sugeruje, że . Landsberg wykazał, że granica rangi wynosi również 7, a Bläser i in. Niedawno rozszerzyłem to w celu wspierania rangi i rangi wsparcia granic. Ranga granicy i ranga wsparcia to słabsze (= mniejsze) pojęcia rangi, które zostały użyte (w przypadku rangi granicznej) lub zaproponowane (w przypadku rangi wsparcia) w algorytmach szybkiego mnożenia macierzy. $R(\langle 2,2,2 \rangle)=7$ $\langle 2,2,2 \rangle$

— Yuval Filmus
źródło

Możesz znaleźć wynik na:

S.Winograd, O mnożeniu macierzy 2 × 2 , Algebra liniowa i Appl. 4 (1971), 381–388, MR0297115 (45: 6173).

— Stella Biderman
źródło