A New Upper Bound For the Growth Factor in Gaussian Elimination with Complete Pivoting

2023/12/02 by Ankit Bisain, Alan Edelman, Bisain, Ankit +3
Computer Science · Earth and Planetary Sciences · Mathematics · #15A23 #65F05 #FOS: Mathematics #Geophysics and Gravity Measurements #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Statistical and numerical algorithms

paper · pdf · doi:10.48550/arxiv.2312.00994

openalex publication_date 2023/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The growth factor in Gaussian elimination measures how large the entries of an LU factorization can be relative to the entries of the original matrix. It is a key parameter in error estimates, and one of the most fundamental topics in numerical analysis. We produce an upper bound of n^{0.2079 ln n +0.91} for the growth factor in Gaussian elimination with complete pivoting -- the first improvement upon Wilkinson's original 1961 bound of 2 n ^{0.25ln n +0.5}.

Related

• Some New Results on the Maximum Growth Factor in Gaussian Elimination
• Gaussian Elimination with Randomized Complete Pivoting
• On a perturbation analysis of Higham squared maximum Gaussian elimination growth matrices
• Average-case analysis of the Gaussian Elimination with Partial Pivoting
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices