Some New Results on the Maximum Growth Factor in Gaussian Elimination

Alan Edelman, John Urschel

Introduction

In numerical linear algebra, Gaussian elimination (GE) is the workhorse for solving linear systems $Ax=b$. However, its numerical stability depends heavily on the "growth factor," which measures how much matrix elements increase in magnitude during the elimination process. While partial pivoting is the standard practical method, its worst-case growth is exponential ($2^{n-1}$). In contrast, complete pivoting (CP) has long been believed to be much more stable. For decades, a "folklore" conjecture suggested that the maximum growth factor $g_n$ for an $n \times n$ matrix under complete pivoting would never exceed $n$.

This paper shatters that long-standing belief. By leveraging modern optimization tools, the authors demonstrate that growth factors can significantly exceed the matrix size, providing strong evidence that the growth is actually super-linear.

The Search for "Monstrous" Matrices

To find matrices that maximize growth, the researchers treated the problem as a constrained optimization task. They utilized the JuMP (Julia for Mathematical Programming) package and the IPOPT solver to "hunt" for worst-case candidates. By running 64 parallel threads with random starting points, they identified matrices that consistently outperformed previous benchmarks.

Tabulated lower bounds for the maximum growth factor $g_n$ for matrix sizes $n=1$ to $75$.

To ensure these numerical results were mathematically sound, the authors developed a Stability Lemma. This theoretical bridge allows them to take a "nearly" completely pivoted matrix (a result of floating-point optimization) and prove the existence of a nearby matrix that is exactly completely pivoted with a similar growth factor.

Key Insights: Beyond Linear Growth

Historically, Hadamard matrices (matrices with $\pm 1$ entries and orthogonal columns) were considered the primary candidates for worst-case growth. However, this study reveals a "slow and steady" strategy: the highest growth doesn't come from large pivots early on, but from a gradual increase in the determinant of sub-matrices that eventually overtakes the growth seen in Hadamard matrices.

One of the most significant findings is the evidence for super-linear growth. For rook pivoting (a middle ground between partial and complete pivoting), the authors proved growth is at least $\Omega(n^{1.669})$. For complete pivoting, their data suggests that the ratio $g(A)/n$ tends toward infinity as $n$ increases.

Results and New Conjectures

The optimization results provided new lower bounds that dwarf previous records. For a matrix of size $n=100$, the authors found a growth factor of 331.71, more than triple the matrix size. This leads to a refinement of the historical conjecture.

Comparison of new growth factor lower bounds against historical results from Gould, highlighting the new conjecture that $g_n > n$ if and only if $n > 10$.

As shown in the comparison above, the authors' results consistently exceed those reported by Gould in the 1990s. They now propose a new conjecture: the growth factor $g_n > n$ if and only if $n > 10$. Furthermore, they established that the limit superior of the ratio of growth to matrix size is at least 3.317.

Conclusion and Future Work

While this paper provides significantly improved lower bounds, the ultimate upper bound for growth in complete pivoting remains one of the great mysteries of numerical analysis. There remains a massive gap between the observed $3n$ growth and Wilkinson’s theoretical upper bound (roughly $n^{\log n / 4}$). The authors suggest that their optimization framework could be used to find even more extreme matrices, potentially leading to a formal mathematical proof that $g(CP_n) = \omega(n)$, the "holy grail" of this 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},
}
Figure