10
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – Kyle Oct 24 '12 at 20:35
12
$\begingroup$

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})$.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ or 2.372 now, right ? $\endgroup$ – Suresh Venkat Oct 12 '12 at 13:41
  • 3
    $\begingroup$ I think it's 2.3727. $\endgroup$ – Markus Bläser Oct 12 '12 at 14:52

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.