Performance Evaluation of the Shifted Cholesky QR Algorithm for Ill-Conditioned Matrices

Authors: Takeshi Fukaya (Hokkaido University), Ramaseshan Kannan (Arup UK), Yuji Nakatsukasa (National Institute of Informatics, Japan), Yusaku Yamamoto (University of Electro-Communications, Japan), Yuka Yanagisawa (Waseda University)

Abstract: The Cholesky QR algorithm, which computes the QR factorization of a matrix, is a simple yet efficient algorithm for high-performance computing. However it suffers from numerical instability. In a recent work, this instability has been remedied by repeating Cholesky QR twice (CholeskyQR2). ChokeskyQR2, however, is still prone to numerical breakdown when applied to ill-conditioned matrices. To overcome this limitation, we introduce a shifting technique to Cholesky QR and use it as a preconditioning step before CholeskyQR2. The key idea is that Cholesky QR with shift reduces the condition number of the input matrix. We call the resulting algorithm shifted CholeskyQR3, which is still simple and only requires double precision arithmetic. In this poster, we present the results of our performance evaluation of shifted CholeskyQR3. We demonstrate that shifted CholeskyQR3 accurately computes the QR factorization of ill-conditioned matrices and that it outperforms other conventional algorithms in execution time.

Best Poster Finalist (BP): no

Poster: pdf
Poster summary: PDF
Reproducibility Description Appendix: PDF


Back to Poster Archive Listing