<p>I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$.</p>

<p>If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination vanishes (say over $\mathbb{F}_2$). From all sets of maximal rank you select the lexicographically smallest. </p>

<p>Now given an $n \times n$-matrix of rank at most $\log n$, we can find a basis of its column span in $\mathrm{AC}_1$ as follows: Divide the columns into two halfves, compute a basis recursively. From these two bases we can compute a common basis using the algorithm from above.  </p>

CC BY-SA 3.0
2017-05-11T15:49:14.070Z
Great! Though I guess that finding the lexicographically first element is already in ACC1[2] and not ACC0[2], right? – Lior Eldar 1 hour ago
Lior Eldar
CC BY-SA 3.0
2017-05-15T12:40:45.013Z
I don't think so. To check whether you are the first basis, you just have to check whether there is no basis to the left of you. This is just an OR.
Markus Bläser
CC BY-SA 3.0
2017-05-11T10:02:13.543Z
2017-05-11T10:02:13.543Z
Markus Bläser
<p>It is known that most computational problems related to linear algebra
can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals
or a finite field, we can compute the rank of $A$, $\det(A)$ or $A^{-1}$, etc. in parallel time $O(\log^2(n))$.</p>

<p>The complexity of these linear-algebra problems remains the same (i.e. in $NC^2$) even if the rank of $A$ is say $n^{\epsilon}$ for some small constant $\epsilon&gt;0$ (just by padding zeros)
but what happens to the complexity of these problems when $A$ has very small rank, i.e. $r = rank(A) \leq \log(n)$?</p>

<p>Clearly, if $A$ is ${\it given}$ to us as a full-rank matrix of dimension $n \times r$ then the complexity drops:
Consider for example the problem of determining whether $A x = b$ for inputs $A,b$ over $\mathbf{F}_2$ for some vector $x$.</p>

<p>One can simply enumerate over all possible column subsets of $A$, and compute $x$ in constant parallel time ($ACC^0[2]$).
However, the problem is that we do not posses such a succinct description from the input.
Naively, trying to brute-force enumerate over all possible column combinations of size $\log(n)$ results in time ${n\choose \log(n)}$ which is quasi-polynomial.</p>

CC BY-SA 3.0
2017-05-11T08:41:29.043Z
I don't understand your question. What is your input and how do you compute $x$ in constant parallel time? What is succinct about the description?
Nikhil
CC BY-SA 3.0
2017-05-11T12:48:52.433Z
In the example above, the input is an $n\times n$ matrix $A$, and a length $n$ vector $b$.  To determine whether there is such $x$ you compute in parallel all partial sums of columns of $A$, and for each one - you check if it is equal to b.  Using unbounded fan-in parity gates each summation can be carried out in constant depth.
Lior Eldar
<ds.algorithms><circuit-complexity><linear-algebra><dc.parallel-comp>
Rank-robustness of the parallel complexity of linear algebra problems
Lior Eldar
# Rank-robustness of the parallel complexity of linear algebra problems

(Asked by: username_0 on 2017-05-10)

It is known that most computational problems related to linear algebra
can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals
or a finite field, we can compute the rank of $A$, $\det(A)$ or $A^{-1}$, etc. in parallel time $O(\log^2(n))$.

The complexity of these linear-algebra problems remains the same (i.e. in $NC^2$) even if the rank of $A$ is say $n^{\epsilon}$ for some small constant $\epsilon>0$ (just by padding zeros)
but what happens to the complexity of these problems when $A$ has very small rank, i.e. $r = rank(A) \leq \log(n)$?

Clearly, if $A$ is ${\it given}$ to us as a full-rank matrix of dimension $n \times r$ then the complexity drops:
Consider for example the problem of determining whether $A x = b$ for inputs $A,b$ over $\mathbf{F}\_2$ for some vector $x$.

One can simply enumerate over all possible column subsets of $A$, and compute $x$ in constant parallel time ($ACC^0[2]$).
However, the problem is that we do not posses such a succinct description from the input.
Naively, trying to brute-force enumerate over all possible column combinations of size $\log(n)$ results in time ${n\choose \log(n)}$ which is quasi-polynomial.

**Tags:** ds.algorithms, circuit-complexity, linear-algebra, dc.parallel-comp
> **Comments:**
> **username_1**: I don't understand your question. What is your input and how do you compute $x$ in constant parallel time? What is succinct about the description?  
> **username_0**: In the example above, the input is an $n\times n$ matrix $A$, and a length $n$ vector $b$.  To determine whether there is such $x$ you compute in parallel all partial sums of columns of $A$, and for each one - you check if it is equal to b.  Using unbounded fan-in parity gates each summation can be carried out in constant depth.  

---

## 1 answers

### Answer by username_2 on 2017-05-11. Score: 4 | Accepted answer

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}\_1$.

If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}\_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination vanishes (say over $\mathbb{F}\_2$). From all sets of maximal rank you select the lexicographically smallest.

Now given an $n \times n$-matrix of rank at most $\log n$, we can find a basis of its column span in $\mathrm{AC}\_1$ as follows: Divide the columns into two halfves, compute a basis recursively. From these two bases we can compute a common basis using the algorithm from above.

> **Comments:**
> **username_0**: Great! Though I guess that finding the lexicographically first element is already in ACC1[2] and not ACC0[2], right? – Lior Eldar 1 hour ago  
> **username_2**: I don't think so. To check whether you are the first basis, you just have to check whether there is no basis to the left of you. This is just an OR.  

---

