Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices (Q7367896)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
No description defined
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices |
No description defined |
Statements
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices (English)
0 references
6 October 2026
0 references
math.NA
0 references
cs.DS
0 references
math.PR
0 references
Daniel A. Spielman
0 references
Xifan Yu
0 references
We prove a new lower bound on the probability of large growth in Gaussian elimination with partial pivoting on $n \times n$ random matrices: $\Omega(\exp(-c \log^2 (ρ)\log(n)))$. This breaks standard conjectures in smoothed and average-case analysis of Gaussian elimination.
0 references
Gaussian Elimination
0 references
Random Matrices
0 references
Lower Bound
0 references
Partial Pivoting
0 references
1 reference
1 reference
1 reference
1 reference
1 reference
