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

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

作　　者：赵学智[1] 叶邦彦[1] 陈统坚[1] 

机构地区：[1]华南理工大学机械与汽车工程学院,广东广州510640

出　　处：《华南理工大学学报（自然科学版）》2010年第1期1-8,共8页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(50875086);广州市科技计划项目(2008J1-C101)

摘　　要：针对传统QR(Quadrature Right-triangle)算法在处理某些大型矩阵的奇异值分解时不收敛的本质原因,提出双向收缩、多次分割的解决对策.研究了对奇异值分解精度有重要影响的从左至右、从下至上的非零元素直线驱逐算法,提出了矩阵分割时子方阵首、末行的搜索算法,进而实现了针对大型矩阵奇异值分解的多次分割、双向收缩QR算法.通过实例比较了不分割与多次分割时算法收敛速度的差异,证实了多次分割双向收缩QR算法具有迭代次数少、迭代过程无停滞、收敛迅速等优点,解决了传统QR算法处理某些大型矩阵的SVD时不收敛的问题,对任何大型矩阵都可实现快速SVD运算.Aimed at the essential reason of the algorithm when it is used to process the singular non-convergence of the traditional QR （Quadrature Right-triangle） value decomposition （SVD） of some large-scale matrixes, a doubledirection shrink and multi-partition method is proposed. In this method, the line dislodgment algorithms of nonzero 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.

关 键 词：奇异值分解 QR算法 大型矩阵 矩阵分割 双向收缩 

分 类 号：TN911.7[电子电信—通信与信息系统] O241.6[电子电信—信息与通信工程]