# Parallel (NC) replacements for Gaussian elimination?

Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine

1. its rank, and
2. a basis for its null-space.

These can be computed easily in time $O(r^2 c)$ by Gauss elimination, but that is a very sequential algorithm.

Are there deterministic parallel (NC, polylogarithmic time, polynomial space) algorithms to compute these?

One may be able to assume that either $r$ or $c$ is small (maybe polylogarithmic) if it helps.

• Isn't Gaussian elimination in $NC^2$? Mar 21, 2014 at 14:08
• @Kaveh, do you have a reference? A google search turned up mostly articles about practical parallel computation (which is hugely important), couldn't find anything complexity-theory oriented. Mar 21, 2014 at 14:42
• It seems that I misremembered. However you can compute characteristic polynomial in $NC^2$ by Berkowitz’s algorithm or by Chistov’s algorithm or by Csanky’s algorithm. Check 1. Joachim von zur Gathen, "Parallel linear algebra", 1993 2. Stuart J. Berkowitz, "On computing the determinant in small parallel time using a small number of processors", 1984 3. Stephen A. Cook, "A taxonomy of problems with fast parallel algorithms" Mar 21, 2014 at 15:43
• 4. Alan Borodin, Stephen A. Cook, and Nick Pippenger, "Parallel computation for well-endowed rings and space-bounded probabilistic machines", 1983. Mar 21, 2014 at 15:58

Yes, it is in $\mathsf{NC}^2$:
The following (earlier) paper shows that solving a system of linear equations reduces to computing the rank, and thus, together with the above result, solving the system (in particular, finding a basis for the nullspace) is also in $\mathsf{NC}^2$: