Złożoność rozwiązywania równań liniowych

Co wiadomo na temat złożoności rozwiązywania układu równań liniowych na pewnym polu skończonym? Wiem, że istnieje$O(n^3)$algorytm (Gauss), który oblicza rozwiązanie, aw przypadku systemów rzadkich istnieją jeszcze lepsze algorytmy. Zastanawiałem się jednak, czy istnieje jakaś teoretyczna charakterystyka złożoności tego problemu. Na przykład jest odpowiedni problem decyzyjny w$\mathbf{NC}$? Czy jest kompletny dla dowolnej klasy złożoności?

Nie jestem pewien, czy jest to pytanie na poziomie badawczym, jakkolwiek rozwiązanie systemów liniowych $\mathbb F_p$ jest $\mathrm{Mod}_p\mathrm L$-kompletny problem, stąd w szczególności jest$\mathrm{NC}^2$. Mówiąc bardziej ogólnie, algebra liniowa jest ponad$\mathbb F_{p^k}$ (przynajmniej dla $k$ naprawiono) można zredukować do $\mathbb F_p$ walizka.

Rezultatem znanym od ponad 30 lat jest to, że eliminacja Guassiana się skończyła $\mathbb F_2$ można tego dokonać przy pomocy różnych dekompozycji $O(n^\omega)$, gdzie $\omega$ to stała mnożenia macierzy.

Bibliografia:

Ibarra, O., Moran, S. i Hui, R. 1982. Uogólnienie algorytmu i aplikacji szybkiej dekompozycji macierzy LUP . Journal of Algorytmy 3, 45 {56.

Jeannerod, C.-P. , Pernet, C. i Storjohann, A. 2011. Profil rang ujawniający eliminację Gaussaina i rozkład macierzy CUP .