pipette
ESEspañol

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

Daniel A. Spielman, Xifan Yu

PreprintClaims a big step

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.