Entry growth in Gaussian elimination

Rikhav Shah, John Urschel

arXiv:2608.19189v2 Primary: math.NA

Abstract

Gaussian elimination is one of the oldest algorithms in mathematics, and the most popular method for solving an unstructured linear system. Its stability in finite precision is controlled by its growth factor, which measures how large the entries produced during elimination can become. Understanding the worst-case behavior of this quantity has been a central problem in numerical analysis since the 1940s. Here we make a significant leap in that understanding, settling several open problems. In particular, we determine the asymptotic behavior of the maximum growth factor under complete and rook pivoting, proving that both are quasi-polynomial in dimension. We also show that the exponential growth under partial pivoting persists for sparse matrices and that randomized partial pivoting suffers the same instability. By contrast, we show that every matrix has a row permutation with polynomial growth, though finding the optimal row permutation is NP-hard.

Disclosure

“• The results of Section 2 began with human only results regarding sparse matrices and partial pivoting proven before the advent of either ChatGPT or Claude. Interaction with AI significantly improved the human only results. • The results of Section 3, were proven with the use of AI. In particular, AI provided explanations of determinantal point processes, examples of stocha”
PDF page 21

Classification: Substantial proof generation
Multiplier: 10
Verified: 2026-08-22T18:17:03.631225Z

Structural counts

Pages 23 pdf

Theorems 17 source

Lemmas 13 source

Propositions 0 source

Corollaries 0 source

Definitions 2 source

Displayed equations 88 source

Bibliography entries 49 source

Appendix pages 0 estimated

Count notes

Source counts use the expanded primary TeX file out.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.