← 研踪 PaperTrailarXiv:2610.08701 · v2
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
首次提交 2026-10-07 01:14
版本更新 2026-11-04 02:23
雷达观测 2026-11-04 23:39
摘要
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ Gaussian random matrices has growth $ρ$ is at least inverse quasi-polynomial: $Ω\left(\exp\left(-c \log^2 \left(\fracρ{\sqrt{n}}\right)\log(n)\right)\right)$ for some constant $c > 0$. In particular, the probability of growth $ρ\ge n^{1/2 + ε}$ is at least $\exp(- O (ε^2 \log^3 (n) ))$. 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 02:23 · 最新观测版本
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ Gaussian random matrices has growth $ρ$ is at least inverse quasi-polynomial: $Ω\left(\exp\left(-c \log^2 \left(\fracρ{\sqrt{n}}\right)\log(n)\right)\right)$ for some constant $c > 0$. In particular, the probability of growth $ρ\ge n^{1/2 + ε}$ is at least $\exp(- O (ε^2 \log^3 (n) ))$. 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.
查看此版本解读 →查看此版本原文 ↗