Rank-revealing decomposition of symmetric indefinite matrices via block anti-triangular factorization

We present an algorithm for computing a symmetric rank revealing decomposition of a symmetric n x n matrix A, as defined in the work of Hansen & Yalamov [9]: we factorize the original matrix into a product A = QMQ(T), with Q orthogonal and M symmetric and in block form, with one of the blocks containing the dominant information of A, such as its largest eigenvalues. Moreover, the matrix M is constructed in a form that is easy to update when adding to A a symmetric rank-one matrix or when appending a row and, symmetrically, a column to A: the cost of such an updating is O(n(2)) floating point operations.