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

  • $\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

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

  • 3
    $\begingroup$ or 2.372 now, right ? $\endgroup$ Oct 12 '12 at 13:41
  • 3
    $\begingroup$ I think it's 2.3727. $\endgroup$ 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.