Average-case analysis of the Gaussian elimination with partial pivoting
This fascinating paper deals with Gaussian elimination with partial pivoting (GEPP). The Gaussian elimination is an algorithm for solving systems of linear equations. In the case of the simplest form of the Gaussian elimination with no pivoting, one is interested in solving a linear system \(Ax = b\) with a square coefficient matrix \(A\) by performing the following \(LU\)-factorization: The matrix \(A\) is represented as the product \(LU\) where \(L\) and \(U\) are lower and upper triangular matrices respectively, and \(x\) is obtained by a combination of forward and back substitutions \(y := L^{-1}b\), \(x := U^{-1}y\). Many strong results on average-case stability of the Gaussian elimination with no pivoting exist in the literature however GEPP lacks matching theoretical guarantees and justifications that it tends to be more stable than the Gaussian elimination with no pivoting. The paper under review makes significant progress on matching theoretical guarantees and justifications that GEPP tends to be more stable than GE with no pivoting. The authors establish that given a random \(n\times n\) standard Gaussian coefficient matrix \(A\), the growth factor of the Gaussian elimination with partial pivoting is at most polynomially large in \(n\) with probability close to one. This says that with probability close to one the number of bits of precision sufficient to solve the system \(Ax = b\) to \(m\) bits of accuracy using GEPP is \(m + O(\log n)\). This improves an earlier estimate \(m + O(\log^2 n)\) of Sanka. The authors also provide tail estimates of the growth factor which can be used to support the empirical observation that GEPP is more stable than Gaussian Elimination with no pivoting.\N\NThe paper is very written with an excellent set of references.
- Average-Case Stability of Gaussian Elimination
- Probabilistic Analysis of Gaussian Elimination Without Pivoting
- Probabilistic analysis of complex Gaussian elimination without pivoting
- On the robustness of Gaussian elimination with partial pivoting
- Stability of the Gauss-Huard algorithm with partial pivoting
- Accuracy and Stability of Numerical Algorithms
- An elementary proof of the restricted invertibility theorem
- Average-Case Stability of Gaussian Elimination
- Concentration inequalities. A nonasymptotic theory of independence
- Condition numbers of random matrices
- Eigenvalues and Condition Numbers of Random Matrices
- Error Analysis of Direct Methods of Matrix Inversion
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- John's decompositions: Selecting a large part
- On sharp bounds for marginal densities of product measures
- On the complete pivoting conjecture for a hadamard matrix of order 12
- Probabilistic Analysis of Gaussian Elimination Without Pivoting
- Random matrices: overcrowding estimates for the spectrum
- Restricted invertibility revisited
- Small ball probabilities for linear images of high-dimensional distributions
- Small ball probability for the condition number of random matrices
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Accuracy and stability of quaternion Gaussian elimination
- Distribution of the number of pivots needed using Gaussian elimination with partial pivoting on random matrices
- Growth factors of orthogonal matrices and local behavior of Gaussian elimination with partial and complete pivoting
- Complete pivoting growth of butterfly matrices and butterfly Hadamard matrices
This page was built for publication: Average-case analysis of the Gaussian elimination with partial pivoting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6550175)
