99
$\begingroup$

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?

$\endgroup$
10
  • 2
    $\begingroup$ (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... $\endgroup$ Dec 22, 2010 at 9:56
  • 2
    $\begingroup$ Maybe the following references would help? lovasz's lecture notes, yap's chapter on determinants (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. $\endgroup$
    – user834
    Dec 22, 2010 at 20:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Dec 23, 2010 at 5:00
  • 4
    $\begingroup$ Curious. Yap's time bound for Bereiss's algorithm is identical to the time bound implied by Edmonds's analysis of Gaussian elimination. $\endgroup$
    – Jeffε
    Dec 23, 2010 at 5:02
  • 2
    $\begingroup$ rjlipton surveyed the area recently & cites Kannan Phd thesis on the subject. a key part of the analysis is wrt Smith normal form $\endgroup$
    – vzn
    Jan 20, 2015 at 16:17

2 Answers 2

46
$\begingroup$

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".

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for the reference! This answers my second question, but not my first. $\endgroup$
    – Jeffε
    Dec 23, 2010 at 4:50
  • 3
    $\begingroup$ 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. $\endgroup$
    – Elias
    Dec 23, 2010 at 8:19
  • $\begingroup$ @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? $\endgroup$ May 31, 2015 at 15:41
16
$\begingroup$

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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.