Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices

DOI10.48550/arXiv.2610.08701MaRDI QIDQ7367896arXivFDO

Authors Xifan Yu, Daniel A. Spielman

Publication date 6 October 2026

Published in arXiv

Tldr We prove a new lower bound on the probability of large growth in Gaussian elimination with partial pivoting on $n \times n$ random matrices: $\Omega(\exp(-c \log^2 (ρ)\log(n)))$. This breaks standard conjectures in smoothed and average-case analysis of Gaussian elimination.

Full work available at URL https://doi.org/10.48550/arXiv.2610.08701

arXiv classification

cs.DSmath.NAmath.PR

Cites work

• Accuracy and Stability of Numerical Algorithms
• Average-case analysis of the Gaussian Elimination with Partial Pivoting
• Average-Case Stability of Gaussian Elimination
• Entry growth in Gaussian elimination
• Error Analysis of Direct Methods of Matrix Inversion
• Numerical Linear Algebra
• Numerical stability in Gaussian elimination
• On the complete pivoting conjecture for a hadamard matrix of order 12
• Searching for Rare Growth Factors Using Multicanonical Monte Carlo Methods
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• The Distribution of the Determinant of a Complex Wishart Distributed Matrix

This page was built for publication: Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7367896)