Printable PDF
Department of Mathematics,
University of California San Diego


Department Colloquium

Konstantin Tikhomirov

Carnegie Mellon University

Average-case analysis of the Gaussian Elimination with Partial Pivoting


The Gaussian Elimination with Partial Pivoting (GEPP) is a classical algorithm for solving systems of linear equations. Empirical evidence strongly suggests that for a typical square coefficient matrix, GEPP is numerically stable. We obtain a (partial) theoretical justification of this phenomenon by showing that, given the random n×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 implies that with probability close to one the number of bits of precision sufficient to solve Ax=b to m bits of accuracy using GEPP is m+O(log(n)), which we conjecture to be optimal by the order of magnitude. We further provide tail estimates of the growth factor which can be used to support the empirical observation that GEPP is more stable than the Gaussian Elimination with no pivoting. Based on joint work with Han Huang.

Tianyi Zheng

February 2, 2023

4:00 PM

APM 6402