On using the Cholesky QR method in the full-blocked one-sided Jacobi algorithm
On using the Cholesky QR method in the full-blocked one-sided Jacobi algorithm
复制标题
论Cholesky QR方法在全分块单边雅可比算法中的应用
DOI：
10.1007/978-3-319-78024-5_53
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Shuhei Kudo and Yusaku Yamamoto
中科院分区：
文献类型：
--
作者：
Shioya Akemi;Yamamoto Yusaku;Shuhei Kudo and Yusaku Yamamoto
单侧Jacobi方法被认为是基于双对角化的奇异值分解（SVD）算法（如QR、分而治之和MRRR）的替代方法，因为它具有精度和可比较的性能。有一种片面Jacobi方法的扩展，称为“全阻塞”方法，它可以通过用矩阵乘法替换一级BLAS操作来进一步提高性能。全块单侧Jacobi方法（OSBJ）的主要部分是计算输入矩阵的一对块列的奇异值分解（SVD）。因此，这种部分奇异值分解的计算方法对OSBJ的精度和性能都具有重要意义。Hari提出了三种计算方法，我们发现其中一种称为“V2”的方法是最快的，并且与其他方法具有相当的精度，该方法使用Cholesky QR方法计算该部分SVD中的QR分解。考虑到Cholesky QR通常被认为是快速但不稳定的算法，这很有趣。在本文中，我们分析了V2的准确性，并解释了其中使用的Cholesky QR方法为什么以及何时可以准确地计算QR分解。我们还展示了与其他计算方法的性能和精度比较。
The one-sided Jacobi method is known as an alternative of the bi-diagonalization based singular value decomposition (SVD) algorithms like QR, divide-and-conquer and MRRR, because of its accuracy and comparable performance. There is an extension of the one-sided Jacobi method called “full-blocked” method, which can further improve the performance by replacing level-1 BLAS like operations with matrix multiplications. The main part of the full-blocked one-sided Jacobi method (OSBJ) is computing the SVD of a pair of block columns of the input matrix. Thus, the computation method of this partial SVD is important for both accuracy and performance of OSBJ. Hari proposed three methods for this computation, and we found out that one of the method called “V2”, which computes the QR decomposition in this partial SVD using the Cholesky QR method, is the fastest and has comparable accuracy with other method. This is interesting considering that Cholesky QR is generally known as fast but unstable algorithm. In this article, we analyze the accuracy of V2 and explain why and when the Cholesky QR method used in it can compute the QR decomposition accurately. We also show the performance and accuracy comparisons with other computational methods.