An upper bound on the growth ratio of Gaussian elimination

AbstractThis note shows that we may adapt the work of J. H. Wilkinson to obtain an upper bound on the growth ratio γ of Gaussian elimination with partial pivoting of an n × n nonsingular real matrix A = (aij) with the following properties: (1) the upper bound ⩽ nγ; (2) the amount of work required to compute the bound is not more than that required to compute ∥U∥1 for any full n × n upper triangular matrix U plus n2 comparisons and one division