RANDOMIZED COMPLETE PIVOTING FOR SOLVING SYMMETRIC INDEFINITE LINEAR SYSTEMS.

The Bunch--Parlett algorithm, the Bunch-Kaufman algorithm, the bounded Bunch-- Kaufman algorithm, and Aasen's algorithm are four well-kno wn methods for solving symmetric indefinite linear systems, yet the last three methods are known to suffer from potential numerical instability. In this work, we develop a randomized complete pivoting (RCP) algorithm for solving symmetric indefinite linear systems of equations. RCP is comparable to the Bunch-Kaufman algorithm and Aasen's algorithm in computational efficiency, but still enjoys theoretical element growth and bounded entries in the factorization comparable to that of the Bunch-Parlett algorithm, up to a theoretical failure probability that exponentially decays with an oversampling parameter. In terms of the boundedness of entries in L, the Bunch-Parlett algorithm, the bounded Bunch-Kaufman algorithm, and Aasen's algorithm have maxi<j |lji| = 1, while the Bunch-Kaufman algorithm does not have a bound. Although we show that RCP only has maxi<j |lji| = O(√n) in theory, our experiments show that this bound is actually O(1). Our finite precision analysis shows that RCP is as numerically stable as Gaussian elimination with complete pivoting, and RCP has been observed to be numerically stable in our extensive numerical experiments. [ABSTRACT FROM AUTHOR]