Accurate Symmetric Indefinite Linear Equation Solvers

The Bunch-Kaufman factorization is widely accepted as the algorithm of choice for the direct solution of symmetric indefinite linear equations; it is the algorithm employed in both LINPACK and LAPACK. It has also been adapted to sparse symmetric indefinite linear systems.While the Bunch--Kaufman factorization is normwise backward stable, its factors can have unusual scaling, with entries bounded by terms depending both on |A| and on $\kappa(A)$. This scaling, combined with the block nature of the algorithm, may degrade the accuracy of computed solutions unnecessarily. Overlooking the lack of a triangular factor bound leads to a further complication in LAPACK such that the LAPACK Bunch--Kaufman factorization can be unstable. We present two alternative algorithms, close cousins of the Bunch-Kaufman factorization, for solving dense symmetric indefinite systems. Both share the positive attributes of the Bunch-Kaufman algorithm but provide better accuracy by bounding the triangular factors. The price of higher...