Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
In the authors' words
We prove that the probability that Gaussian elimination with partial pivoting on random matrices has growth is at least inverse quasi-polynomial: for some constant . 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.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.