大型矩阵奇异值分解的多次分割双向收缩快速QR算法

针对传统QR算法在处理某些大矩阵的奇异值分解时可能不收敛的本质原因，提出采用双向收缩、多次分割的解决对策。研究了在一般矩阵数值计算文献中被忽视的、然而对奇异值分解精度有重要影响的细节如从左至右、从下至上的非零元素直线驱逐算法，提出了矩阵分割时子阵首、末行搜索算法，在这些基础上实现了完整的针对大型矩阵奇异值分解的多次分割、双向收缩QR算法。通过实例比较和分析了不分割与多次分割双向收缩QR算法的收敛速度的差异，证实了多次分割双向收缩QR算法具有迭代次数少、迭代过程无停滞、收敛迅速等优点，解决了传统QR算法处理某些大矩阵的SVD时可能不收敛的问题，对任何大矩阵都可实现快速SVD运算。

Multi-Partition and Double-Direction Shrink QR Algorithm for Singular Value Decomposition of Large-Scale Matrix

Aimed at the essential reason of the non-convergence of the traditional QR(Quadrature Right-triangle) algorithm when it is used to process the singular value decomposition (SVD) of some large-scale matrixes, a double-direction shrink and multi-partition method is proposed. In this method, the line dislodgment algorithms of non-zero element from left to right and from down to up, which greatly influence the accuracy of SVD, are investigated, and a searching algorithm for the first and the last rows of the sub-matrix is put forward to realize the partition of the main matrix. Thus, a multi-partition and double-direction shrink QR algorithm for the SVD of large-scale matrix is implemented. An example is then presented to reveal the difference of convergence speed between the non-partition and the multi-partition QR algorithms. The results indicate that the proposed algorithm realizes a smooth iteration process with less iteration number and high convergence speed, overcomes the non-convergence of the traditional QR algorithm, and realizes the high-speed SVD computation of any large-scale matrix.