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