The anti-triangular factorization of symmetric matrices

Indefinite symmetric matrices occur in many applications, such as optimization, least squares problems, partial differential equations and variational problems. In these applications one is often interested in computing a factorization of the indefinite matrix that puts into evidence the inertia of the matrix or possibly provides an estimate of its eigenvalues. In this paper we propose an algorithm that provides this information for any symmetric indefinite matrix by transforming it to a block anti-triangular form using orthogonal similarity transformations. We also show that the algorithm is backward stable and has a complexity that is comparable to existing matrix decompositions for dense indefinite matrices.