Average-case analysis of the Gaussian elimination with partial pivoting (Q6550175)

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.