大规模最小二乘奇异值分解的并行处理方法  

Parallel processing for solving large-scale least square problem by singular value decomposition

作　　者：吴文波[1] 姚新宇[1] 刘丽丽[2] 

机构地区：[1]国防科学技术大学信息系统与管理学院,长沙410073 [2]国防科学技术大学机电工程与自动化学院,长沙410073

出　　处：《计算机应用研究》2014年第11期3253-3256,3265,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61374185)

摘　　要：大规模最小二乘问题求解中,直接进行奇异值分解会产生巨大的内存需求以及漫长的计算时间。为解决该问题,提出了一种基于迭代的并行处理方法。该方法利用奇异值分解降维的特性,通过迭代不断减小矩阵规模,直到可以直接使用奇异值分解求解。在迭代过程中,将矩阵分解为许多足够小的子矩阵,并行处理其奇异值分解过程,从而提升运行速度。实验结果表明,该方法即使是串行处理,也使得大规模最小二乘奇异值分解的时间成本及空间成本大大降低;而并行处理在双机条件下加速比接近200%。For large-scale least square problem,applying SVD directly on the matrix required huge memory demanding,and it was time consuming,this paper proposed an iteration based parallel processing method for solving this problem.This method took advantage of matrix dimension decreasing feature of SVD,and the matrix became smaller by iteration,until the matrix was small enough which could be solved by SVD directly.In the iteration,it divided the matrix into lots of submatirces that were small enough to be solved by SVD,they could be processed in parallel,so that it improved the processing speed.Experiment results show that,the proposed method can greatly decrease the requirements in time and space of solving large-scale least square prob-lem even processed serially;and the speedup ratio of parallel processing in the circumstance of two nodes can be close to 200%.

关 键 词：最小二乘 奇异值分解 迭代 并行处理 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]