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)$$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 O ( n 2 ) dla wszystkich pierścieni. Czy ktoś może wyjaśnić, jak to działa?$O(n^2)$$O(n^2)$

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

Załóżmy, że i A B v = C v . Niech D = A B - C . D jest niezerową macierzą, dla której D v = 0 . Jakie jest prawdopodobieństwo, że to nastąpi? Niech D [ i $AB \neq C$$ABv = Cv$$D = AB - C$$D$$Dv = 0$ będzie wartością niezerową. Z założenia ∑ j D [ i ′ , j ] v [ j ] = $D[i',j']$$\sum_{j} D[i',j] v[j] = 0$. Z prawdopodobieństwem , v [ j " ] = 1 , 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. - D [ i ′ , j ′ ] . Teraz, prawdopodobieństwo złego wydarzenia - D [ I ' , j ' ] = Σ j ≠ j ' D [ I ' , j ] v [ j ] jest co najwyżej 1 /$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 D [ i ′ , j ] musi być niezerowe. v [ j ] odpowiada tym innym niezerowym wpisom. Nawet jeśli ustawimy wszystkie te v [ j ] z wyjątkiem jednego z nich optymalnie , nadal istnieje równe prawdopodobieństwo dla ostatniego wynoszącego 0 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 1 / 4 , udało nam się dowiedzieć, że D v ≠ 0 , gdy D jest niezerowe. (Uwaga v [ j ] i v [ j ′ ] są niezależnie wybrane dla j ≠ j ′ .)$-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?