Average-Case Stability of Gaussian Elimination

Abstract

Gaussian elimination with partial pivoting is unstable in the worst case: the “growth factor” can be as large as $2^{n - 1} $, where n is the matrix dimension, resulting in a loss of $n - 1$ bits of precision. It is proposed that an average-case analysis can help explain why it is nevertheless stable in practice. The results presented begin with the observation that for many distributions of matrices, the matrix elements after the first few steps of elimination are approximately normally distributed. From here, with the aid of estimates from extreme value statistics, reasonably accurate predictions of the average magnitudes of elements, pivots, multipliers, and growth factors are derived. For various distributions of matrices with dimensions $n\leqq 1024$, the average growth factor (normalized by the standard deviation of the initial matrix elements) is within a few percent of $n^{2/3} $ for partial pivoting and approximately $n^{1/2} $ for complete pivoting. The average maximum element of the residual wi...