PreprintCC BY 4.0arXiv
Instability of Gaussian elimination is exponentially rare (proof of partial result)
Abstract
Gaussian elimination with partial pivoting is the standard algorithm for solving a dense n× n system of linear equations Ax=b. The ``growth factor'' ρ for this process may be as large as 2n−1, and when ρ is large, the algorithm is unstable. Nevertheless, long experience has shown that Gaussian elimination is resoundingly stable in practice. Experiments indicate that among random matrices with independent normally distributed entries, growth factors ρ≫ n1/2 are in a precise sense exponentially rare. Here we take a step toward confirming this observation by proving it not for the full growth factor, which depends on all the entries of the upper-triangular factor U, but for the corner entry unn.
Related
- Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
- Instability and Morse Index of Exponentially Subelliptic Harmonic Maps
- Stochastic Homogenization of Schrödinger Equations with Exponentially Mixing Sub-Gaussian Potentials
- An Omega result for partial sums of the Riemann zeta function
- Entry growth in Gaussian elimination
BibTeX
@misc{trefethen2026instability,
title = {{Instability of Gaussian elimination is exponentially rare (proof of partial result)}},
author = {Lloyd N. Trefethen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04761},
eprint = {2610.04761},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04761},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Instability of Gaussian elimination is exponentially rare (proof of partial result)
AU - Lloyd N. Trefethen
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04761
UR - https://arxiv.org/abs/2610.04761
AB - Gaussian elimination with partial pivoting is the standard algorithm for solving a dense n× n system of linear equations Ax=b. The ``growth factor'' ρ for this process may be as large as 2^n−1, and when ρ is large, the algorithm is unstable. Nevertheless, long experience has shown that Gaussian elimination is resoundingly stable in practice. Experiments indicate that among random matrices with independent normally distributed entries, growth factors ρ≫ n^1/2 are in a precise sense exponentially rare. Here we take a step toward confirming this observation by proving it not for the full growth factor, which depends on all the entries of the upper-triangular factor U, but for the corner entry u_nn^.
ER -