What is known about the complexity of solving a system of linear equations over some finite field? I know that there exists an $O(n^3)$ algorithm (Gauss) that computes a solution and that for sparse systems there are even better algorithms. However, I was wondering if there was some comlexity-theoretic characterization of this problem. For example, is the corresponding decision problem in $\mathbf{NC}$? Is it complete for any complexity class?
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More generally, linear algebra over $\mathbb F_{p^k}$ (at least for $k$ fixed) can be reduced to the $\mathbb F_p$ case.
answered Jul 29, 2014 at 14:53
$\begingroup$
$\endgroup$
A result known for over 30 years is that Guassian Elimination over $\mathbb F_2$ can be done by a various decompositions which takes $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.
References:
Ibarra, O. , Moran, S. , and Hui, R. 1982. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms 3 , 45{56.
Jeannerod, C.-P. , Pernet, C. , and Storjohann, A. 2011. Rank profile revealing Gaussain elimination and the CUP matrix decomposition.
