Accurate symmetric indefinite linear equation solvers

The Bunch-Kaufman factorization is widely accepted as the algorithm of choi ce 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 fac torization is normwise backward stable, its factors can have unusual scalin g, with entries bounded by terms depending both on parallel to A parallel t o and on k(A). This scaling, combined with the block nature of the algorith m, may degrade the accuracy of computed solutions unnecessarily. Overlookin g 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 f actorization, for solving dense symmetric indefinite systems. Both share th e positive attributes of the Bunch-Kaufman algorithm but provide better acc uracy by bounding the triangular factors. The price of higher accuracy can be kept low by choosing between our two algorithms. One is appropriate as t he replacement for the blocked LAPACK Bunch-Kaufman factorization; the othe r would replace the LINPACK-like unblocked factorization in LAPACK. Solving sparse symmetric indefinite systems is more problematic. We conclud e that the Bunch-Kaufman algorithm cannot be rescued effectively in the spa rse case. Imposing the constraint of bounding the triangular factors leads naturally to one particular version of the Duff-Reid algorithm, which we sh ow gives better accuracy than Liu's sparse variant of the Bunch-Kaufman alg orithm. We extend the work of Duff and Reid in two respects that often prov ide higher efficiency: a more effective procedure for finding pivot blocks and a stable extension to pivot blocks of size larger than two.