Jaka jest najbardziej ogólna struktura weryfikacji produktu matrycowego w czasie

W 1979 r. Freivalds wykazał, że weryfikacja produktów matrycowych w dowolnym polu może być przeprowadzona w losowym czasie . Bardziej formalnie, biorąc pod uwagę trzy macierze A, B i C, z wpisami z pola F, problem sprawdzania, czy AB = C ma losowy algorytm czasowy . $O(n^2)$ $O(n^2)$

Jest to interesujące, ponieważ najszybszy znany algorytm mnożenia macierzy jest wolniejszy niż ten, dlatego sprawdzanie, czy AB = C jest szybsze niż obliczanie C.

Chcę wiedzieć, jaka jest najbardziej ogólna struktura algebraiczna, nad którą weryfikacja iloczynu macierzowego nadal ma algorytm czasu (losowego) . Ponieważ oryginalny algorytm działa na wszystkich polach, myślę, że działa również na wszystkich domenach integralnych. $O(n^2)$

Najlepszą odpowiedzią, jaką mogłem znaleźć na to pytanie, były podklubie Równoważności między ścieżkami, macierzą i problemami trójkąta , w których powiedziano: „weryfikacja iloczynu macierzy przez pierścienie może być wykonana w losowym czasie [BK95]”. ([BK95]: M. Blum i S. Kannan. Projektowanie programów, które sprawdzają ich pracę. J. ACM, 42 (1): 269–291, 1995.) $O(n^2)$

Po pierwsze, czy pierścienie są najbardziej ogólną strukturą, na której ten problem ma losowy algorytm ? Po drugie, nie widziałem, jak wyniki [BK95] pokazują algorytm czasowy wszystkich pierścieni. Czy ktoś może wyjaśnić, jak to działa? $O(n^2)$ $O(n^2)$

ds.algorithms linear-algebra matrix-product

— Robin Kothari
źródło

Głupie pytanie: czy oczywiste jest, że weryfikacja deterministyczna jest tak trudna jak rozmnażanie? Co jeśli otrzymasz nie tylko A, B i C, ale także certyfikat kompaktowy; czy to coś pomaga?

— Jukka Suomela,

@Jukka: Uważam, że najlepszy algorytm deterministyczny dla tego problemu nie jest szybszy niż mnożenie macierzy, ale nie wiem, czy istnieje powód, dla którego powinno tak być. Jeśli chodzi o drugie pytanie, jeśli AB nie jest równe C, to działa krótki certyfikat: wpis C jest niepoprawny oraz odpowiedni wiersz A i kolumna B.

— Robin Kothari

Oto szybki argument, dlaczego działa on nad pierścieniami. Podane macierze , , $A$ $B$ $C$ , weryfikujemy , wybierając losowy wektor bitów , a następnie sprawdzając, czy . To wyraźnie przechodzi jeżeli . $A B = C$ $v$ $ABv = Cv$ $AB = C$

Załóżmy, że i . Niech . jest niezerową macierzą, dla której . Jakie jest prawdopodobieństwo, że to nastąpi? Niech $AB \neq C$ $ABv = Cv$ $D = AB - C$ $D$ $Dv = 0$ będzie wartością niezerową. Z założenia $D[i',j']$ $\sum_{j} D[i',j] v[j] = 0$ . Z prawdopodobieństwem , , to mamy $1/2$ $v[j'] = 1$

. $D[i',j'] + \sum_{j\neq j'} D[i',j] v[j] = 0$

Każdy pierścień w ramach operacji dodawania jest grupą addytywną, więc istnieje unikalna odwrotność , tj. . Teraz, prawdopodobieństwo złego wydarzenia jest co najwyżej $D[i',j']$ $-D[i',j']$ $-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$ $1/2$ . (Jednym ze sposobów na to jest „zasada odroczonych decyzji”: aby suma była równa , przynajmniej jedno inne musi być niezerowe. odpowiada tym innym niezerowym wpisom. Nawet jeśli ustawimy wszystkie te z wyjątkiem jednego z nich optymalnie , nadal istnieje równe prawdopodobieństwo dla ostatniego wynoszącego lub $-D[i',j']$ $D[i',j]$ $v[j]$ $v[j]$ $0$ $1$ , Ale tylko jedna z tych wartości może sprawić, że ostateczną kwotę równą ). Tak więc z prawdopodobieństwem co najmniej , udało nam się dowiedzieć, że , gdy jest niezerowe. (Uwaga i są niezależnie wybrane dla .) $-D[i',j']$ $1/4$ $Dv \neq 0$ $D$ $v[j]$ $v[j']$ $j \neq j'$

Jak widać, powyższy argument zależy od odejmowania. Więc to nie będzie działać (na przykład) na dowolnych semutycznych przemiennych. Być może mógłbyś rozluźnić multiplikatywne właściwości struktury algebraicznej i nadal uzyskać wynik?

— Ryan Williams
źródło

Fajnie dzięki. Widzę twój punkt widzenia, że istnieje możliwość zmniejszenia ograniczeń struktury multiplikatywnej. Dla mojej informacji, czy nie jest to ten sam algorytm, co w oryginalnej pracy Freivalds?

— Robin Kothari,

1 / 2

$1/2$