<p>The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the 
book Algebraic Complexity Theory by Bürgisser, Clausen &amp; Shokrollahi.
So it can be done in time $O(n^{2.38})$.</p>

CC BY-SA 3.0
2012-10-12T13:41:11.270Z
or 2.372 now, right ?
Suresh Venkat
CC BY-SA 3.0
2012-10-12T14:52:58.037Z
I think it's 2.3727.
Markus Bläser
CC BY-SA 3.0
2012-10-12T08:53:25.747Z
2012-10-12T10:49:26.837Z
2012-10-12T10:49:26.837Z
Markus Bläser
<p>I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.</p>

CC BY-SA 3.0
2012-10-24T20:35:53.903Z
I can see one way to do Gaussian Elimination of matrix M in O(n^2 rank(M)) time.  Is there a way to do that faster?
Kyle
<ds.algorithms><linear-algebra><matrices>
What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?
GMB
# What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?

(Asked by: username_0 on 2012-10-12)

I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.

**Tags:** ds.algorithms, linear-algebra, matrices
> **Comments:**
> **username_1**: I can see one way to do Gaussian Elimination of matrix M in O(n^2 rank(M)) time.  Is there a way to do that faster?  

---

## 1 answers

### Answer by username_2 on 2012-10-12. Score: 12 | Accepted answer

The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the
book Algebraic Complexity Theory by Bürgisser, Clausen & Shokrollahi.
So it can be done in time $O(n^{2.38})$.

> **Comments:**
> **username_3**: or 2.372 now, right ?  
> **username_2**: I think it's 2.3727.  

---

