Source-linked AI summary
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
Daniel A. Spielman, Xifan Yu
TL;DR
The paper addresses how often GEPP on Gaussian random matrices can produce large growth, a quantity tied to numerical accuracy. It analyzes covariance updates through elimination and proves an inverse-quasi-polynomial lower bound on that probability. The authors say this bound, combined with known upper bounds, suggests an approximately log-normal growth distribution.
Problem
GEPP’s growth factor can contribute to inaccurate solutions, and the paper studies the probability of large growth on random matrices.
Source: §1 · pp. 1–2Method
The proof tracks covariance updates for active columns through successive GEPP elimination steps.
Source: §2.4 · p. 6Results
The probability of growth at least ρ is at least exp(−345 log^2(ρ) log(n)).
Source: §1 · p. 2Takeaways & Limitations
Combined with known upper bounds, the result suggests that GEPP’s growth distribution is approximately log-normal.
Source: §1 · p. 2The authors have not optimized the constants and note that choices of parameters and larger n and ρ could improve the constant.
Source: §5.1 · p. 20
Abstract
from arXiv · showhide
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.
1 Introduction
GEPP remains widely used despite worst-case instability, and its growth factor can contribute to inaccurate solutions. The paper disproves conjectures of exponential decay in growth probability, establishing an inverse-quasi-polynomial lower bound and reporting an AI-assisted step in the proof’s development.
1 Introduction
- GEPP is commonly used despite worst-case instability because it is fast, while its growth factor can make numerical solutions inaccurate and can reach 2n−1.The paper relates relative error to machine precision, a polynomial in n, the matrix condition number, and the growth factor; it notes that standard precision would suffice for only about 50 dimensions at the worst-case growth.Source: §1 · pp. 1–2
- Experiments and prior conjectures proposed exponential decay in growth probability, which the authors say their results disprove.The passage cites conjectures for both Gaussian matrices and the more general smoothed setting.Source: §1 · p. 2
- Theorem 2.2 says the probability of growth at least ρ is at least exp(−345 log2(ρ) log(n)); combined with known upper bounds, this suggests an approximately log-normal growth-rate distribution.Source: §1 · p. 2
Role of Artificial Intelligence
- The authors report that an AI-produced proof of a weak form of a lemma led them to a determinant-based strengthening, which was key to the improved inverse-quasi-polynomial lower bound.The earlier condition-number-based argument yielded a lower bound of exp(−O(log^3(ρ))) for large growth.Source: Role of Artificial Intelligence · p. 3
2 Preliminaries
This material introduces GEPP and growth, states a lower bound on the probability of large growth, compares it with prior upper bounds, and outlines a covariance-based proof strategy.
2 Preliminaries
- The preliminaries specify matrix, vector, norm, condition-number, and submatrix notation used in the analysis.They define the operator norm and condition number and describe indexing and deletion notation.Source: §2 · p. 3
2.1 Gaussian Elimination with Partial Pivoting
- GEPP factors a nonsingular matrix as PA = LU, selecting the largest-magnitude entry in each active column as pivot; the growth factor is related to numerical error.The factorization permits solving systems through triangular solves, and the paper describes growth as a factor in bounds on numerical error.Source: §2.1 · pp. 3–5
2.2 Main Result: lower bound on probability of GEPP having large growth
- The paper establishes a lower bound on the probability that GEPP has large growth for independent standard-normal matrix entries, and says the bound applies across a range from below expected growth to exponential in n.The supplied theorem passage does not include the bound’s full formula.Source: §2.2 · p. 5
2.3 Detailed Comparison with Previous Results
- The paper’s comparison says its lower bound rules out a decay rate better than inverse-quasipolynomial, while the cited upper bound does not prevent growth on the order of n^O(log n); the exact bounds do not match.For Gaussian entries, the cited upper bound decays like exp(−c log(n) log(ρ/n^O(log n))).Source: §2.3 · p. 6
2.4 Proof Strategy
- The proof strategy tracks covariance matrices of active columns and iterates a chance of increasing their operator norm by a factor of at least 7/5, yielding a large entry with probability approximately n^−O(δ^2).The argument sets δ approximately log_(7/5) ρ and applies the increase argument over the last δ steps.Source: §2.4 · p. 6
3 Covariance Update Process
The covariance update process describes how GEPP transforms the distribution of the active trailing matrix at each elimination step.
3 Covariance Update Process
- The kth elimination step pivots the first row, forms multipliers from the pivot column, and projects away the eliminated row and column to obtain the next active matrix.The vectors q and r encode the multipliers and their row permutation in the update description.Source: §3 · pp. 6–7
- Conditioning on the first column leaves the remaining columns with the updated covariance, while row and column permutations and deletion of an all-zero row and column preserve the operator norm.The update operator depends only on the first column of M(k).Source: §3 · p. 7
- If the columns of M(k) are independent N(0, Σ(k)) vectors, the columns of M(k+1) remain independent normal vectors with covariance Σ(k+1).The paper uses this update process to analyze GEPP’s growth factor.Source: §3 · p. 7
4 Mathematical Tools
Section 4 assembles Gaussian probability tools and covariance-update bounds used to establish the paper’s main result. It covers Gaussian and Wishart facts, conic-event comparison, and controls on covariance growth and determinants.
4.1 Facts about Gaussians
- The Gaussian preliminaries define standard-normal density and cumulative distribution notation and record facts about chi-squared and Wishart distributions.The section also introduces a comparison inequality for conic events under general and isotropic Gaussian measures.Source: §4.1 · pp. 8–9
- For conic events, the section presents a comparison inequality relating their probability under a general Gaussian distribution to that under an isotropic Gaussian.A set is conic when it is closed under multiplication by positive scalars.Source: §4.1 · p. 8
4.2 Covariance Update Tools
- A sufficient-condition proposition relates covariance growth to a top eigenvector and a vector normalized at its largest-magnitude coordinate.A separate proposition gives deterministic determinant control for a vector selected by its largest-magnitude coordinate.Source: §4.2 · p. 10
- Conditioned on the first k−1 columns, the remaining entries of the kth column are normally distributed with covariance Σ(k) = I + XXᵀ, and Σ(k) ⪰ I.The covariance update tools analyze the GEPP process after its preceding row swaps and pivot choices.Source: §4.2 · pp. 10–11
- The determinant analysis uses the Wishart distribution of the first k−1 columns and a union bound over row subsets to control low-determinant events.The supplied passages identify the event that some subset of k−1 rows has squared determinant at most z.Source: §4.2 · pp. 11–12
- The section also states deterministic determinant control for a nonzero vector using its largest-magnitude coordinate.The proposition specifies the index attaining the maximum and normalizes the vector by that coordinate.Source: §4.2 · p. 13
5 Proof of Main Result
The proof builds a probabilistic covariance-growth argument for GEPP and connects covariance growth to the upper-triangular factor. It then combines bounds on the growth-factor numerator and denominator to prove the main result.
5 Proof of Main Result
- For 1≤k≤n−3, given positive-definite d×d Σ(k) ⪰ I_d (d=n−k+1), the update samples y∼N(0,Σ(k)), selects i=argmax_j|y[j]|, sets r=y/y[i], and produces (d−1)×(d−1) Σ(k+1).Source: §5 · p. 16
- The proof decomposes an event across r covariance updates and bounds conditional probabilities using the lower bound Σ(i)⪰I.The event setup tracks covariance norms over successive updates.Source: §5 · pp. 16–17
- A lower bound on the covariance norm is connected to GEPP growth because the largest-magnitude entry of the first column is selected as the pivot and placed on U's diagonal.The argument conditions on the covariance at step n−d+1 and the preceding history.Source: §5 · p. 18
5.1 Proof of Theorem 2.2
- For T=20, the proof combines bounds on the growth-factor numerator and denominator, with r≥100 and n≥r+22.The proof then considers ρ in a stated range bounded by ρ_min and ρ_max.Source: §5.1 · pp. 19–20
- The proof does not optimize its constants; it notes that changing parameters and considering larger n and ρ could improve them.The remark identifies T as one parameter that could be increased.Source: §5.1 · p. 20