Matrix Computations and Scientific Computing Seminar: Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems

Seminar | April 26 | 11 a.m.-12 p.m. | 380 Soda Hall

 Yuehua Feng, Xiamen University, China

 Department of Mathematics

Bunch-Kaufman's partial pivoting (BKPP) algorithm and Aasen's algorithm are two of the most widely used methods for solving symmetric indefinite linear systems, yet they both suffer from occasional numerical instability due to potentially exponential element growth. In this work, we develop a randomized complete pivoting (RCP) algorithm for solving symmetric indefinite linear systems. RCP is comparable to BKPP and Aasen's algorithm in computational efficiency. However, RCP is numerically stable, with element growth comparable to that of complete-pivoting, up to a failure probability that exponentially decays with an oversampling parameter. Numerical experimental results support these claims and will be discussed.