Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Isn't Gaussian elimination in $NC^2$? –  Kaveh Mar 21 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 at 14:42
2  
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 at 15:43
1  
4. Alan Borodin, Stephen A. Cook, and Nick Pippenger, "Parallel computation for well-endowed rings and space-bounded probabilistic machines", 1983. –  Kaveh Mar 21 at 15:58

1 Answer 1

up vote 6 down vote accepted

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

Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. 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. Information and Control 52(3):241-25, 1982.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.