Istnieją dowody, że mnożenie macierzy jest w

39

Powszechnie uważa się, że dla wszystkich ϵ>0 możliwe jest pomnożenie dwóch macierzy n×n w czasie O(n2+ϵ) . Trochę dyskusji jest tutaj .

Zapytałem niektórych ludzi, którzy są bardziej zaznajomieni z badaniami, czy myślą, że istnieje k>0 niezależne od n tak że istnieje algorytm O(n2logkn) do mnożenia macierzy i wydaje się, że w przeważającej części mają intuicję, że odpowiedź brzmi „nie”, ale nie mogła wyjaśnić, dlaczego. Oznacza to, że wierzą, że możemy to zrobić w czasie O(n2.001) , ale nie w czasie O(n2log100n) .

Jakie są powody, by sądzić, że nie ma algorytmu O(n2logkn) przy stałym k>0 ?

Brian
źródło

Odpowiedzi:

29

Istnieje algorytm mnożenia macierzy N×N0.172 macierz N0.172×N w operacjach arytmetycznych N2polylog(N) . Główna tożsamość zastosowana w tym dokumencie pochodzi z pracy Coppersmitha „Szybkie mnożenie prostokątnych macierzy”, ale wyjaśnienie, dlaczego prowadzi do polilogu N2polylog(N) zamiast N2+ϵ znajduje się w dodatku do artykułu Williamsa , „Nowe algorytmy oraz dolne granice dla obwodów z liniowymi bramkami progowymi ".

Działa to tylko dlatego, że tożsamość Coppersmith ma dodatkową strukturę, z której można skorzystać, a nowsze algorytmy MM nie wydają się mieć takiej struktury. To powiedziawszy, nie jestem pewien, dlaczego nie można spodziewać się rozszerzenia tego podejścia na mnożenie macierzy N×N×N

Josh Alman
źródło
11

AϵO(n2+ϵ)O(n2poly(logn))

O(n2poly(logn))

Joshua Grochow
źródło
3
Nie jestem pewien, w jaki sposób posiadanie rodziny nie prowadzi prawdopodobnie do O (n ^ 2poly (log n)), ponieważ jeśli można wystarczająco dobrze opisać rodzinę, można wybrać coraz bardziej wydajnych członków rodziny dla większej liczby n. Jedynym powodem, dla którego nie jest to prawdopodobne O (n ^ 2poly (log N)), jest fakt, że zaangażowane stałe byłyby prawdopodobnie bardzo duże, ale nie jest oczywiste, że tak właśnie jest.
JoshuaZ
1
O(n2+x)ε>0O(n2+ε)
1
@JoshuaZ Podejrzewam, że innym, jeszcze dziwniejszym sposobem może być niepowodzenie, gdyby wybranie / zbudowanie członka rodziny zajęło więcej niż O (n ^ 2 poli (log n)) czasu - np. Być może potrzebny jest kod O (1 / e), aby zaimplementuj algorytm O (n ^ (2 + e)) lub coś takiego. Czy to nie byłoby dzikie?
Daniel Wagner,