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 B ∈ R n × p wynosi O ( m n p ) (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 n są znacznie mniejsze niż p , i miałem nadzieję, aby uzyskać lepszą złożoność niż liniowego w p , na koszt dokonywania uzależnienie od m i n 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 m = n = p (gdy wszystkie macierze są kwadratami).$p$$m=n=p$

Klasyczna praca Coppersmitha pokazuje, że dla niektórych można pomnożyć macierz n × n α przez macierz n α × n w operacjach arytmetycznych ˜ O ( n 2 ) . 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.