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).