The Growth-Factor Bound for the Bunch-Kaufman Factorization Is Tight
Alex Druinsky, Sivan Toledo · SIAM Journal on Matrix Analysis and Applications · 2011
We show that the growth-factor bound in the Bunch–Kaufman factorization method is essentially tight. The method factors a symmetric matrix [Formula: see text] into [Formula: see text], where [Formula: see text] is a permutation matrix, [Formula: see text] is lower triangular, and [Formula: see text] is block diagonal with 1-by-1 and 2-by-2 diagonal blocks. The method uses one of several partial pivoting rules that ensure bounded in the elements of the reduced matrix and the factor [Formula: see text] (growth in [Formula: see text] is not bounded). We show that the exponential bound is essentially tight, thereby solving a question that has been open since 1977.