Some New Results on the Maximum Growth Factor in Gaussian Elimination

Alan Edelman, John Urschel

TL;DR

This paper shatters a long-standing "folklore" conjecture in numerical linear algebra by proving that the maximum growth factor in Gaussian elimination with complete pivoting can significantly exceed the matrix size $n$. Using modern optimization tools, the authors found matrices where the growth factor is larger than $3n$ for $n=100$ and provided strong evidence that growth is actually super-linear.

What Problem Does This Paper Address?

When you solve a linear system $Ax=b$ using Gaussian elimination, the algorithm transforms the matrix through a series of steps. The "growth factor" measures how much the elements of the matrix increase in magnitude during this process. If the growth factor is large, round-off errors can explode, leading to a total loss of numerical precision.

For "partial pivoting" (the standard method), the worst-case growth is known to be $2^{n-1}$—an exponential nightmare that rarely happens in practice. However, for "complete pivoting" (a more rigorous search for the best pivot), a famous folklore conjecture suggested that the growth factor would never exceed $n$. While a counterexample for $n=13$ was found in the early 90s, progress stalled for 30 years. This paper reopens the case, investigating just how large this growth can truly get and whether it follows a linear or super-linear trend.

Methods

The authors combined heavy-duty numerical optimization with rigorous mathematical proofs:

  • Numerical Search: They used the JuMP (Julia for Mathematical Programming) package and the IPOPT solver to treat the search for the worst-case matrix as a constrained optimization problem. By running 64 parallel threads with random starting points, they "hunted" for matrices that maximize growth.
  • The Stability Lemma: To bridge the gap between "noisy" floating-point results and "pure" mathematics, they developed a "Stability Lemma." This allows them to take a matrix that is nearly completely pivoted (a numerical result) and prove there exists a nearby matrix that is exactly completely pivoted with a similar growth factor.
  • Theoretical Reductions: They proved that the maximum growth over restricted sets (like matrices containing only 0s and 1s) is polynomially related to the growth over all real matrices.

Datasets

This is a theoretical and computational mathematics paper, so it does not use traditional training datasets. Instead, the "data" consists of:

  • Optimization Results: A tabulated set of lower bounds for the maximum growth factor for every matrix size from $n=1$ to $n=75$, plus $n=100$.
  • Hadamard Matrices: The authors specifically tested Hadamard matrices (matrices with $\pm 1$ entries and orthogonal columns), which were historically thought to be the "worst-case" candidates.

Key Insights and Ideas

  • The "Slow and Steady" Strategy: By analyzing the pivots of their $n=100$ matrix, the authors found that the highest growth doesn't come from "greedy" large pivots early on. Instead, the worst-case matrices exhibit a "slow and steady" increase in the determinant of sub-matrices, eventually overtaking the growth seen in Hadamard matrices.
  • Super-linear Growth: The most significant "aha moment" is the evidence for super-linear growth. For rook pivoting (a middle ground between partial and complete pivoting), they proved growth is at least $\Omega(n^{1.669})$. For complete pivoting, their data strongly suggests the ratio $g(A)/n$ goes to infinity as $n$ grows.
  • Universality of Entries: They showed that the specific values allowed in a matrix (e.g., restricting entries to a small set $S$) don't change the fundamental nature of the growth factor problem. If growth is super-polynomial for real matrices, it's super-polynomial for binary matrices too.

Key Results

  • New Lower Bounds: For $n=100$, they found a growth factor of 331.71, more than triple the matrix size.
  • Refining the Conjecture: They propose a new conjecture: the growth factor $g_n > n$ if and only if $n \ge 11$.
  • Asymptotic Growth: They established that the $\limsup$ of the ratio of growth to matrix size is at least 3.317.
  • Rook Pivoting: They provided the first proof of super-linear growth for rook pivoting, showing $g(RP_n) > \frac{1}{641}n^{1.669}$.

Limitations and Future Work

While the paper provides much better lower bounds, the upper bound remains a massive mystery. The gap between the observed $3n$ growth and Wilkinson’s theoretical upper bound (which is roughly $n^{\log n / 4}$) is still enormous.

The authors suggest that future researchers might use their optimization framework to find even more "monstrous" matrices. Additionally, while they have provided strong numerical evidence for super-linear growth in complete pivoting, a formal mathematical proof for the $g(CP_n) = \omega(n)$ conjecture remains the "holy grail" of this sub-field.

Summary updated

Abstract

This paper combines modern numerical computation with theoretical results to improve our understanding of the growth factor problem for Gaussian elimination. On the computational side we obtain lower bounds for the maximum growth for complete pivoting for $n=1:75$ and $n=100$ using the Julia JuMP optimization package. At $n=100$ we obtain a growth factor bigger than $3n$. The numerical evidence suggests that the maximum growth factor is bigger than $n$ if and only if $n \ge 11$. We also present a number of theoretical results. We show that the maximum growth factor over matrices with entries restricted to a subset of the reals is nearly equal to the maximum growth factor over all real matrices. We also show that the growth factors under floating point arithmetic and exact arithmetic are nearly identical. Finally, through numerical search, and stability and extrapolation results, we provide improved lower bounds for the maximum growth factor. Specifically, we find that the largest growth factor is bigger than $1.0045n$ for $n>10$, and the lim sup of the ratio with $n$ is greater than or equal to $3.317$. In contrast to the old conjecture that growth might never be bigger than $n$, it seems likely that the maximum growth divided by $n$ goes to infinity as $n \rightarrow \infty$.
BibTeX
@article{edelman2024some,
  author = {Alan Edelman and John Urschel},
  title = {{Some New Results on the Maximum Growth Factor in Gaussian Elimination}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2024},
  url = {https://openreview.net/forum?id=1TnSJAgv2C},
}

Loading related content...

Figure