<p>I think the answer to your first question is also $\widetilde O(n^3 \log( \|A\| + \|b\|))$ due to the following arguments: Edmonds' paper does not describe a variant of Gaussian elimination but it proves that any number computed in a step of the algorithm is a determinant of some submatrix of A. By <a href="http://books.google.de/books?id=zEzW5mhppB8C&amp;redir_esc=y">Schrijver's book on Theory of Linear and Integer Programming</a> we know that if A's encoding needs b bits (b should be in $\widetilde O(\log( \|A\|)$) then any of its subdeterminants needs at most 2b bits (Theorem 3.2). In order to make Gaussian elimination a polynomial time algorithm we have to care about the computed quotients: We have to cancel out common factors from every fraction we compute in any intermediate step and then all numbers have encoding length linear in the encoding length of A.</p>

CC BY-SA 3.0
2013-11-15T08:58:51.297Z
2013-11-15T08:58:51.297Z
Matthias Walter
<p>I think the answer is $\widetilde O(n^3 \log( \|A\| + \|b\|))$, where
we omit the (poly)logarithmic factors.  The bound is presented in
"W. 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 a
paper by Dixon: "Exact solution of linear equations using P-adic
expansions, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Number 1,
137-141".</p>

CC BY-SA 3.0
2015-05-31T15:41:12.050Z
@Elias, what is the definition of the norm in that expression? Is it the largest coefficient in absolute size? Is it the bit size? Also, is this result for arbitrary rational matrices?
Juan Bermejo Vega
CC BY-SA 2.5
2010-12-23T04:50:05.730Z
Thanks for the reference!  This answers my second question, but not my first.
Jeffε
CC BY-SA 2.5
2010-12-23T08:19:46.620Z
If you use pivoting then the bitsize of the intermediate results in Gaussian elimination (GE) is polynomial, there is no exponential explosion. I think this is Bareiss result.

As for the complexity of GE, there is an algorithm in the book of Gathen and Gerhard, "Modern Computer Algebra" for computing the determinant of a matrix $A$, that is based on GE, modular arithmetic and Chinese remainder theorem (Sec. 5.5, pp 101-105). The complexity is $O(n^4 \log^2\|A\|)$. I think a factor of $n$ could be saved using fast arithmetic.
If I am not wrong, this is the bound that user834 mentioned.
Elias
CC BY-SA 2.5
2010-12-22T20:15:24.013Z
2010-12-22T20:15:24.013Z
Elias
<p>In an answer to an <a href="https://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science">earlier question</a>, I mentioned the common but false belief that <a href="http://arxiv.org/abs/0907.2397" rel="noreferrer" title="Not actually discovered by Gauss, of course">“Gaussian”</a> 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:</p>

<p>$$\begin{bmatrix}
2 &amp; 0 &amp; 0 &amp; \cdots &amp; 0 \\
1 &amp; 2 &amp; 0 &amp; \cdots &amp; 0 \\
1 &amp; 1 &amp; 2 &amp; \cdots &amp; 0 \\
\vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots\\
1 &amp; 1 &amp; 1 &amp; \cdots &amp; 2 \\
\end{bmatrix}$$</p>

<p>If we use a version of the elimination algorithm without division, which only adds <em>integer</em> 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.</p>

<p><b>But what <em>is</em> the actual time complexity of Gaussian elimination?</b>  Most combinatorial optimization authors seem to be happy with “strongly polynomial”, but I'm curious what the polynomial actually is.</p>

<p><a href="http://pretty.structures.free.fr/talks/(7.1.1)Solving.pdf" rel="noreferrer">A 1967 paper of Jack Edmonds</a> 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”.)</p>

<p>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?</p>

<p>More generally: <strong>What is the running time (on the integer RAM) of the fastest algorithm known for solving arbitrary systems of linear equations?</strong></p>

CC BY-SA 3.0
2015-01-20T16:17:45.110Z
rjlipton [surveyed](https://rjlipton.wordpress.com/2015/01/14/forgetting-results/) the area recently & cites Kannan Phd thesis on the subject. a key part of the analysis is wrt [Smith normal form](http://en.wikipedia.org/wiki/Smith_normal_form)
vzn
CC BY-SA 3.0
2016-04-06T21:01:26.170Z
Is all this discussion considering $n$ to be the number of unknowns in the linear system? Because considering $n$ to be the number of elements of a dense matrix, I could only get $O(n^{1.5})$ arithmetic operations instead of the expected $O(n^3)$.
lvella
CC BY-SA 3.0
2016-04-07T14:23:46.447Z
@lvella   I'm assuming that the matrix has $n$ rows and $n$ columns, which is fairly standard.
Jeffε
CC BY-SA 2.5
2010-12-21T22:53:07.980Z
Interesting question!
Daniel Apon
CC BY-SA 2.5
2010-12-22T09:56:03.383Z
(inserting violent handwave) couldn't you get around the large integer problem in this particular case using hashing modulo small prime tricks ? the algorithm would be randomized, but still.. Admittedly this doesn't answer the question you asked...
Suresh Venkat
CC BY-SA 2.5
2010-12-22T18:04:56.937Z
@Suresh: That would (probably) tell you the rank of the matrix, but (maybe) not the actual solution to the linear system.  Right?
Jeffε
CC BY-SA 2.5
2010-12-22T18:23:11.930Z
yes, that's true. the more I think about it, the more intriguing it gets. Maybe the right model is some kind of fast oracle that given (i,j) returns the entry in the 'eliminated' matrix, where the fast oracle is randomized and uses the Edmonds observation ? (sorry, hard to keep my hand from waving)
Suresh Venkat
CC BY-SA 2.5
2010-12-22T20:59:37.737Z
Maybe the following references would help? [lovasz's lecture notes](http://www.cs.bu.edu/faculty/gacs/courses/cs530/lectures/exact-Gauss.pdf), [yap's chapter on determinants](http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz) (Yap gives $O(n^3 M_B[n (\log n + L)])$ bit complexity for determinant calculation via Bareiss's algorithm).  From Yap's book (exercise 10.1.1 (iii)), I was under the impression that it was unknown whether Gaussian reduction gave intermediate values that grew exponentially in bit size, but now I'm not sure.
user834
CC BY-SA 2.5
2010-12-23T05:00:51.217Z
The standard Gaussian elimination algorithm divides the pivot row by the pivot element before reducing later rows.  The open question refers to this standard version.  The example I gave at the beginning of my question uses a different variant, which does NOT divide through by the pivot element.
Jeffε
CC BY-SA 2.5
2010-12-23T05:02:17.190Z
Curious.  Yap's time bound for Bereiss's algorithm is *identical* to the time bound implied by Edmonds's analysis of Gaussian elimination.
Jeffε
<cc.complexity-theory><ds.algorithms><reference-request><linear-algebra>
What is the actual time complexity of Gaussian elimination?
Jeffε
# What is the actual time complexity of Gaussian elimination?

(Asked by: username_0 on 2010-12-21)

In an answer to an [earlier question](https://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science), I mentioned the common but false belief that [“Gaussian”](http://arxiv.org/abs/0907.2397 "Not actually discovered by Gauss, of course") 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](http://pretty.structures.free.fr/talks/(7.1.1)Solving.pdf) 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?**

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, linear-algebra

> **Comments:**
> **username_3**: Interesting question!  
> **username_4**: (inserting violent handwave) couldn't you get around the large integer problem in this particular case using hashing modulo small prime tricks ? the algorithm would be randomized, but still.. Admittedly this doesn't answer the question you asked...  
> **username_0**: @Suresh: That would (probably) tell you the rank of the matrix, but (maybe) not the actual solution to the linear system.  Right?  
> **username_4**: yes, that's true. the more I think about it, the more intriguing it gets. Maybe the right model is some kind of fast oracle that given (i,j) returns the entry in the 'eliminated' matrix, where the fast oracle is randomized and uses the Edmonds observation ? (sorry, hard to keep my hand from waving)  
> **username_5**: Maybe the following references would help? [lovasz's lecture notes](http://www.cs.bu.edu/faculty/gacs/courses/cs530/lectures/exact-Gauss.pdf), [yap's chapter on determinants](http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz) (Yap gives $O(n^3 M_B[n (\log n + L)])$ bit complexity for determinant calculation via Bareiss's algorithm).  From Yap's book (exercise 10.1.1 (iii)), I was under the impression that it was unknown whether Gaussian reduction gave intermediate values that grew exponentially in bit size, but now I'm not sure.  
> **username_0**: The standard Gaussian elimination algorithm divides the pivot row by the pivot element before reducing later rows.  The open question refers to this standard version.  The example I gave at the beginning of my question uses a different variant, which does NOT divide through by the pivot element.  
> **username_0**: Curious.  Yap's time bound for Bereiss's algorithm is *identical* to the time bound implied by Edmonds's analysis of Gaussian elimination.  
> **username_1**: rjlipton [surveyed](https://rjlipton.wordpress.com/2015/01/14/forgetting-results/) the area recently & cites Kannan Phd thesis on the subject. a key part of the analysis is wrt [Smith normal form](http://en.wikipedia.org/wiki/Smith_normal_form)  
> **username_2**: Is all this discussion considering $n$ to be the number of unknowns in the linear system? Because considering $n$ to be the number of elements of a dense matrix, I could only get $O(n^{1.5})$ arithmetic operations instead of the expected $O(n^3)$.  
> **username_0**: @username_2   I'm assuming that the matrix has $n$ rows and $n$ columns, which is fairly standard.  

---

## 2 answers

### Answer by username_7 on 2010-12-22. Score: 48 | Accepted answer

I think the answer is $\widetilde O(n^3 \log( \|A\| + \|b\|))$, where
we omit the (poly)logarithmic factors. The bound is presented in
"W. 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 a
paper by Dixon: "Exact solution of linear equations using P-adic
expansions, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Number 1,
137-141".

> **Comments:**
> **username_0**: Thanks for the reference!  This answers my second question, but not my first.  
> **username_7**: If you use pivoting then the bitsize of the intermediate results in Gaussian elimination (GE) is polynomial, there is no exponential explosion. I think this is Bareiss result.  As for the complexity of GE, there is an algorithm in the book of Gathen and Gerhard, "Modern Computer Algebra" for computing the determinant of a matrix $A$, that is based on GE, modular arithmetic and Chinese remainder theorem (Sec. 5.5, pp 101-105). The complexity is $O(n^4 \log^2\|A\|)$. I think a factor of $n$ could be saved using fast arithmetic. If I am not wrong, this is the bound that username_5 mentioned.  
> **username_8**: @username_7, what is the definition of the norm in that expression? Is it the largest coefficient in absolute size? Is it the bit size? Also, is this result for arbitrary rational matrices?  

---

### Answer by username_6 on 2013-11-15. Score: 17

I think the answer to your first question is also $\widetilde O(n^3 \log( \|A\| + \|b\|))$ due to the following arguments: Edmonds' paper does not describe a variant of Gaussian elimination but it proves that any number computed in a step of the algorithm is a determinant of some submatrix of A. By [Schrijver's book on Theory of Linear and Integer Programming](http://books.google.de/books?id=zEzW5mhppB8C&redir_esc=y) we know that if A's encoding needs b bits (b should be in $\widetilde O(\log( \|A\|)$) then any of its subdeterminants needs at most 2b bits (Theorem 3.2). In order to make Gaussian elimination a polynomial time algorithm we have to care about the computed quotients: We have to cancel out common factors from every fraction we compute in any intermediate step and then all numbers have encoding length linear in the encoding length of A.


---

