An alternative full-pivoting algorithm for the factorization of indefinite symmetric matrices

摘要

This paper presents an algorithm for the factorization of indefinite symmetric matrices that factors any symmetric matrix A into the form LDLT, with D diagonal and L triangular, with its subdiagonal filled with zeros. The algorithm is based on Jacobi rotations, as opposed to the widely used permutation methods (Aasen, Bunch–Parlett, and Bunch–Kaufman). The method introduces little increase in computational cost and provides a bound on the elements of the reduced matrices of order 2nf(n), which is smaller than that of the Bunch–Parlett method (≃3nf(n)), and similar to that of Gaussian elimination with full pivoting (nf(n)). Furthermore, the factorization method is not blocked. Although the method presented is formulated in a full-pivoting scheme, it can easily be adapted to a scheme similar to that of the Bunch–Kaufman approach. A backward error analysis is also presented, showing that the elements of the error matrix can be bounded in terms of the elements of the reduced matrices.