Performance Evaluation of the Shifted Cholesky QR Algorithm for Ill-Conditioned Matrices
TimeThursday, November 15th8:30am - 5pm
DescriptionThe 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.