Jianwei Xiao

Jianwei Xiao, Ming Gu, Julien Langou

Factorizing large matrices by QR with column pivoting (QRCP) is substantially more expensive than QR without pivoting, owing to communication costs required for pivoting decisions. In contrast, randomized QRCP (RQRCP) algorithms have proven themselves empirically to be highly competitive with high-performance implementations of QR in processing time, on uniprocessor and shared memory machines, and as reliable as QRCP in pivot quality. We show that RQRCP algorithms can be as reliable as QRCP with failure probabilities exponentially decaying in oversampling size. We also analyze efficiency differences among different RQRCP algorithms. More importantly, we develop distributed memory implementations of RQRCP that are significantly better than QRCP implementations in ScaLAPACK. As a further development, we introduce the concept of and develop algorithms for computing spectrum-revealing QR factorizations for low-rank matrix approximations, and demonstrate their effectiveness against leading low-rank approximation methods in both theoretical and numerical reliability and efficiency.

Jianwei Xiao, Ming Gu

Kernel methods represent some of the most popular machine learning tools for data analysis. Since exact kernel methods can be prohibitively expensive for large problems, reliable low-rank matrix approximations and high-performance implementations have become indispensable for practical applications of kernel methods. In this work, we introduce spectrum-revealing Cholesky factorization, a reliable low-rank matrix factorization, for kernel matrix approximation. We also develop an efficient and effective randomized algorithm for computing this factorization. Our numerical experiments demonstrate that this algorithm is as effective as other Cholesky factorization based kernel methods on machine learning problems, but significantly faster.

Yuehua Feng, Jianwei Xiao, Ming Gu

The Bunch-Kaufman algorithm and Aasen's algorithm are two of the most widely used methods for solving symmetric indefinite linear systems, yet they both are known to suffer from occasional numerical instability due to potentially exponential element growth or unbounded entries in the matrix factorization. In this work, we develop a randomized complete pivoting (RCP) algorithm for solving symmetric indefinite linear systems. RCP is comparable to the Bunch-Kaufman algorithm and Aasen's algorithm in computational efficiency, yet enjoys theoretical element growth and bounded entries in the factorization comparable to that of complete-pivoting, up to a theoretical failure probability that exponentially decays with an oversampling parameter. 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.