Accurate Symmetric Indefinite Linear Equation Solvers

Authors:
  • CACleve Ashcraft
    Cleve Ashcraft
  • RGRoger G. Grimes
    Roger G. Grimes
  • JLJohn G. Lewis
    John G. Lewis

Abstract
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...

This publication has 21 references indexed in Scilit: