I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.
10
$\begingroup$
$\endgroup$
-
$\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$
$\endgroup$
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
-
3
