4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Isn't Gaussian elimination in $NC^2$? $\endgroup$
    – Kaveh
    Mar 21 '14 at 14:08
  • $\begingroup$ @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. $\endgroup$
    – David Harris
    Mar 21 '14 at 14:42
  • 3
    $\begingroup$ 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" $\endgroup$
    – Kaveh
    Mar 21 '14 at 15:43
  • 2
    $\begingroup$ 4. Alan Borodin, Stephen A. Cook, and Nick Pippenger, "Parallel computation for well-endowed rings and space-bounded probabilistic machines", 1983. $\endgroup$
    – Kaveh
    Mar 21 '14 at 15:58
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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