Dowody na to, że mnożenie macierzy można przeprowadzić w czasie kwadratowym?

59

Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:ω

Jakie mamy powody, by sądzić, że ?ω=2

Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je uznać za dowód na .ω=2

Naiwnie wydaje mi się, że jest to klasyczny przykład, w którym społeczność ma tylko nadzieję, że wynik jest prawdziwy wyłącznie ze względów estetycznych. Chciałbym wiedzieć, czy tak jest w istocie w tym przypadku.

Steve Flammia
źródło
12
ω=2
5
ω>2
2
@ Ryan, miejmy nadzieję, że Strassen czyta cstheory.stackexchange. :)
Steve Flammia
3
Ω(nlogn)ω=22
5
ωω

Odpowiedzi:

20

322/3322/3

(W przypadku ich innych hipotez 4.7, które są teorią grupową, nie znam żadnych podobnych dowodów wiarygodności poza intuicją.)

Po drugie, zgadzam się z Amirem Shpilką, że ciąg przeszłych algorytmów ma nieco ad hoc charakter. Jedną z miłych rzeczy w podejściu grupowym jest to, że prawie wszystkie (nie całkiem) poprzednie algorytmy można sformułować w tym podejściu. Chociaż różne konstrukcje teoretyczne w grupach w [CKSU] mogą wydawać się nieco doraźne na zewnątrz, w kontekście ram teoretycznych grup wydają się znacznie bardziej naturalne i mniej ad-hoc (przynajmniej dla mnie) niż wiele innych poprzednie algorytmy.

Joshua Grochow
źródło
Kiedy myślę o pojemności, myślę o niezależnych zestawach i klikach. Jaki jest słownik między USP a wyraźną konstrukcją podstawowego wykresu i czy istnieje struktura tych wykresów?
T ....
28

ω=2ω=2

Amir Shpilka
źródło
20

ω=2

ABnnC=ABC(i,j)=k=1nA(i,k)B(k,j)ABnC=ABC(i)=k=1nA(k)B(ik)O~(n)O(n2)O~(n2)algorytm czasowy mnożenia macierzy. Pytanie brzmi: jaki jest analog transformacji Fouriera, który może pomóc w mnożeniu macierzy?

arnab
źródło
-1

O(n2log(n2))ω=2

Chad Brewbaker
źródło
1
ωcO(nc)O(n2log10n)2Ω(n2logn)
@SashoNikolov Dziękujemy za zwrócenie na to uwagi. Czy ktoś próbował trenować sieć neuronową dla logicznego matmula A * B = C? [Wpisy A, Wpisy B, Wpisy C] -> Bool (poprawne lub niepoprawne pomnożenie). Ciekawe, jakie obwody wymyśla przyzwoity gradient / spadek; jeśli wyćwiczone obwody mają atraktory w pobliżu głównych rozkładów. Na 3x3, 4x4, 5x5, 6x6 wydaje się, że godzina GPU dałaby ciekawe wyniki.
Chad Brewbaker