Entry growth in Gaussian elimination
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. In contrast, we show that every non-singular matrix has a row permutation with polynomial growth, though finding the optimal row permutation is NP-hard.
Related
- Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
- Instability of Gaussian elimination is exponentially rare (proof of partial result)
- Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding
- Tight instances of the Lonely Runner Conjecture: one-entry modifications and the growth of speeds
- Elimination of René Peschmann's 968 Remaining Hard Fibers for the Perfect Cuboid Problem
BibTeX
@misc{shah2026entry,
title = {{Entry growth in Gaussian elimination}},
author = {Rikhav Shah and John Urschel},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.19189},
eprint = {2608.19189},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.19189},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Entry growth in Gaussian elimination
AU - Rikhav Shah
AU - John Urschel
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.19189
UR - https://arxiv.org/abs/2608.19189
AB - 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. In contrast, we show that every non-singular matrix has a row permutation with polynomial growth, though finding the optimal row permutation is NP-hard.
ER -