Accurate symmetric indefinite linear equation solvers. (English) Zbl 0923.65010

The paper is devoted to solving efficiently and accurately linear systems \(Ax=b\) with symmetric indefinite matrix \(A\). When \(A\) is dense, the three well known methods – the algorithms of J. R. Bunch and L. Kaufman [Math. Comput. 31, 163-179 (1977; Zbl 0355.65023)], J. R. Bunch and B. N. Parlett [SIAM J. Numer. Anal. 8, 639-655 (1971; Zbl 0199.49802)], and J. O. Aasen [BIT 11, 233-242 (1971; Zbl 0242.65032)] – are revised carefully, demonstrating thereby that overlooking the lack of the triangular part in the factorization may lead to unstability. The authors present two alternative algorithms – the bounded Bunch-Kaufman and the fast Bunch-Parlett methods, which overcome the drawbacks of their predecessors providing more accurate solutions with minimal costs.
A set of examples is reported demonstrating the effectiveness of the new algorithms. In the case of sparse matrices \(A\) a new version of the algorithm of I. S. Duff and J. K. Reid [ACM Trans. Math. Software 9, 302-325 (1983; Zbl 0515.65022)] is introduced which gives better accuracy than J. W. H. Liu’s sparse modification [ACM Trans. Math. Software 13, 173-182 (1987; Zbl 0628.65017)] of Bunch-Kaufman’s method. The new algorithm is based on a more effective procedure for finding \(2 \times 2\) and larger pivot blocks. A variety of numerical examples on sparse problems are presented as well.


65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
Full Text: DOI