In an answer to an earlier question, I mentioned the common but false belief that Gaussian elimination runs in $O(n^3)$ time.  While it is obvious that the algorithm uses $O(n^3)$ arithmetic operations, careless implementation can create numbers with exponentially many bits.  As a simple example, suppose we want to diagonalize the following matrix:$$\begin{bmatrix}2 & 0 & 0 & \cdots & 0 \\1 & 2 & 0 & \cdots & 0 \\1 & 1 & 2 & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots\\1 & 1 & 1 & \cdots & 2 \\\end{bmatrix}$$If we use a version of the elimination algorithm without division, which only adds integer multiples of one row to another, and we always pivot on a diagonal entry of the matrix, the output matrix has the vector $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$ along the diagonal.But what is the actual time complexity of Gaussian elimination?  Most combinatorial optimization authors seem to be happy with strongly polynomial, but I'm curious what the polynomial actually is.A 1967 paper of Jack Edmonds describes a version of Gaussian elimination (possibly due to Gauss) that  runs in strongly polynomial time.  Edmonds' key insight is that every entry in every intermediate matrix is the determinant of a minor of the original input matrix.  For an $n\times n$ matrix with $m$-bit integer entries, Edmonds proves that his algorithm requires integers with at most $O(n(m+\log n))$ bits.  Under the reasonable assumption that $m=O(\log n)$, Edmonds' algorithm runs in $O(n^5)$ time if we use textbook integer arithmetic, or in $\tilde{O}(n^4)$ time if we use FFT-based multiplication, on a standard integer RAM, which can perform $O(\log n)$-bit arithmetic in constant time.  (Edmonds didn't do this time analysis; he only claimed that his algorithm is good.)Is this still the best analysis known?  Is there a standard reference that gives a better explicit time bound, or at least a better bound on the required precision?More generally: What is the running time (on the integer RAM) of the fastest algorithm known for solving arbitrary systems of linear equations?
What is the actual time complexity of Gaussian elimination?
ds.algorithms;reference request;linear algebra
I think the answer is $\widetilde O(n^3 \log( \|A\| + \|b\|))$, wherewe omit the (poly)logarithmic factors.  The bound is presented inW. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann,G. Villard. Solving sparse integer linear systems. Proc. ISSAC'06,Genova, Italy, ACM Press, 63-70, July 2006, but it is based on apaper by Dixon: Exact solution of linear equations using P-adicexpansions, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Number 1,137-141.