Złożoność obliczeniowa mnożenia macierzy

Szukam informacji o złożoności obliczeniowej mnożenia macierzy prostokątnych macierzy. Wikipedia stwierdza, że złożoność pomnożenia przez wynosi (mnożenie podręcznika). $A \in \mathbb{R}^{m \times n}$ $B \in \mathbb{R}^{n \times p}$ $O(mnp)$

Mam przypadek, w którym i są znacznie mniejsze niż , i miałem nadzieję, aby uzyskać lepszą złożoność niż liniowego w , na koszt dokonywania uzależnienie od i gorsze niż liniowy. $m$ $n$ $p$ $p$ $m$ $n$

Jakieś pomysły?

Dzięki.

Uwaga: powodem, dla którego mam nadzieję, że będzie to możliwe, jest dobrze znany wynik zależności mniejszej niż sześcienna w jeśli (gdy wszystkie macierze są kwadratami). $p$ $m=n=p$

— informujący się
źródło

Złożoność algorytmu (sekwencyjnego) nie może być mniejsza niż wielkość jego wyniku. Czy dla swojego problemu możesz reprezentować dane wejściowe i wyjściowe za pomocą przestrzeni podliniowej w p?

— Colin McQuillan

czy elementy są w większości niezerowe czy często zerowe? tj. rzadki? co z pewnością prowadzi do różnych optymalizacji. wydaje się również, że SVD [rozkład wartości w liczbie pojedynczej] może być istotny w oparciu o bieżącą odpowiedź odnoszącą się do przybliżeń.

— vzn

Klasyczna praca Coppersmitha pokazuje, że dla niektórych można pomnożyć macierz macierz w operacjach arytmetycznych . Jest to kluczowy składnik ostatniego słynnego wyniku Ryana Williamsa. $\alpha > 0$ $n \times n^\alpha$ $n^\alpha \times n$ $\tilde{O}(n^2)$

François le Gall ostatnio ulepszył pracę Coppersmitha, a jego praca została właśnie przyjęta na FOCS 2012. Aby zrozumieć tę pracę, będziesz potrzebować wiedzy na temat teorii złożoności algebraicznej. Artykuł Virginii Williams zawiera kilka istotnych wskazówek. W szczególności praca Coppersmitha jest całkowicie opisana w książce Teoria złożoności algebraicznej .

$n \times N$ $N \times n$ $N \gg n$

Podstawowym podejściem jest próbkowanie matryc (odpowiada to losowej redukcji wymiarowości) i pomnożenie znacznie mniejszych próbkowanych matryc. Sztuką jest dowiedzieć się, kiedy i w jakim sensie daje to dobre przybliżenie. W przeciwieństwie do poprzedniej części pracy, która jest całkowicie niepraktyczna, algorytmy próbkowania są praktyczne, a nawet niezbędne do obsługi dużych ilości danych.

— Yuval Filmus
źródło

Tylko uwaga: wiadomo (od listopada 2010 r.), Że mnożenie macierzy prostokątnej nie jest konieczne do rozwiązania ACC SAT. (Co jest dobre, ponieważ prostokątna matryca mult jest „galaktyczna” i złożona.)

— Ryan Williams