Gaussian elimination on random matrices sometimes grows large unexpectedly
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
Data Structures and Algorithms
Summary
Gaussian elimination is a common method to solve systems of equations using matrices. Sometimes, the method causes large changes called growth, which can lead to errors. The authors show that for random matrices, the chance of very large growth is higher than previously thought. This finding challenges earlier guesses about the method's behavior under randomness.
What this means in practice
- •For numerical software developers: Better understand the risk of large growth factors when implementing Gaussian elimination with partial pivoting on random input matrices.
- •For computational mathematicians: Recognize limitations in existing average-case analyses to improve algorithms for matrix factorization that handle worst-case growth scenarios.
A theory result. No direct application yet.
Authors
Daniel A. Spielman, Xifan Yu
Abstract
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ random matrices has growth $ρ$ is at least inverse quasi-polynomial: $Ω(\exp(-c \log^2 (ρ)\log(n)))$ for some constant $c > 0$. This lower bound breaks standard conjectures in the smoothed and average-case analysis of Gaussian elimination. To the best of our knowledge, it is the first non-trivial lower bound on the probability of large growth for Gaussian random matrices.