Metraipolis › archive › dc_4f9050d693aa
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices — arXiv:2610.08701
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.08701
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:51:19.580Z
- SHA-256 of the archived text
aa95577b90521042b7ffb2886371081a232531751eb03c891866b7ee7202e0d9- Stable URL of this page
https://metraipolis.com/documento/dc_4f9050d693aa
How to cite
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices — arXiv:2610.08701 — arXiv (en), https://arxiv.org/abs/2610.08701 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4f9050d693aa (Metraipolis archive dc_4f9050d693aa, sha256 aa95577b90521042b7ffb2886371081a232531751eb03c891866b7ee7202e0d9)
BibTeX
@misc{dc4f9050d693aa,
title = {Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices — arXiv:2610.08701},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.08701},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4f9050d693aa; sha256 aa95577b90521042b7ffb2886371081a232531751eb03c891866b7ee7202e0d9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08701. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ random matrices has growth $\rho$ is at least inverse quasi-polynomial: $\Omega(\exp(-c \log^2 (\rho)\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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno). Categorie arXiv: Numerical Analysis (math.NA) ; Data Structures and Algorithms (cs.DS); Probability (math.PR). Pagina del lavoro: https://arxiv.org/abs/2610.08701 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T11:21:39.670Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).