<p>Yes, it is in $\mathsf{NC}^2$: </p>

<blockquote>
  <p>Mulmuley, K. <a href="http://dx.doi.org/10.1007/BF02579205">A fast parallel algorithm to compute the rank of a matrix over an arbitrary field</a>. Combinatorica 7 (1987), no. 1, 101–104. </p>
</blockquote>

<p>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$:</p>

<blockquote>
  <p>Allan Borodin, Joachim von zur Gathen, John Hopcroft. <a href="http://dx.doi.org/10.1016/S0019-9958(82)90766-5">Fast parallel matrix and GCD computations</a>. Information and Control 52(3):241-25, 1982.</p>
</blockquote>

CC BY-SA 3.0
2014-03-21T15:45:50.463Z
2014-03-21T15:45:50.463Z
Joshua Grochow
<p>Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine  </p>

<ol>
<li>its rank, and </li>
<li>a basis for its null-space.</li>
</ol>

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

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

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

CC BY-SA 3.0
2014-03-21T14:08:06.313Z
Isn't Gaussian elimination in $NC^2$?
Kaveh
CC BY-SA 3.0
2014-03-21T14:42:32.500Z
@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
CC BY-SA 3.0
2014-03-21T15:43:36.137Z
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
CC BY-SA 3.0
2014-03-21T15:58:09.407Z
4. Alan Borodin, Stephen A. Cook, and Nick Pippenger, "Parallel computation for well-endowed rings and space-bounded probabilistic machines", 1983.
Kaveh
<cc.complexity-theory><complexity-classes><linear-algebra><dc.parallel-comp><matrices>
Parallel (NC) replacements for Gaussian elimination?
David Harris
# Parallel (NC) replacements for Gaussian elimination?

(Asked by: username_0 on 2014-03-21)

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.

**Tags:** cc.complexity-theory, complexity-classes, linear-algebra, dc.parallel-comp, matrices

> **Comments:**
> **username_1**: Isn't Gaussian elimination in $NC^2$?  
> **username_0**: @username_1, 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.  
> **username_1**: 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"  
> **username_1**: 4. Alan Borodin, Stephen A. Cook, and Nick Pippenger, "Parallel computation for well-endowed rings and space-bounded probabilistic machines", 1983.  

---

## 1 answers

### Answer by username_2 on 2014-03-21. Score: 8 | Accepted answer

Yes, it is in $\mathsf{NC}^2$:

> Mulmuley, K. [A fast parallel algorithm to compute the rank of a matrix over an arbitrary field](http://dx.doi.org/10.1007/BF02579205). Combinatorica 7 (1987), no. 1, 101–104.

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$:

> Allan Borodin, Joachim von zur Gathen, John Hopcroft. [Fast parallel matrix and GCD computations](http://dx.doi.org/10.1016/S0019-9958(82)90766-5). Information and Control 52(3):241-25, 1982.


---

