# 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$? – Kaveh Mar 21 '14 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. – David Harris Mar 21 '14 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" – Kaveh Mar 21 '14 at 15:43
• 4. Alan Borodin, Stephen A. Cook, and Nick Pippenger, "Parallel computation for well-endowed rings and space-bounded probabilistic machines", 1983. – Kaveh Mar 21 '14 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$: