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

摘要

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%.%大规模最小二乘问题求解中，直接进行奇异值分解会产生巨大的内存需求以及漫长的计算时间。为解决该问题，提出了一种基于迭代的并行处理方法。该方法利用奇异值分解降维的特性，通过迭代不断减小矩阵规模，直到可以直接使用奇异值分解求解。在迭代过程中，将矩阵分解为许多足够小的子矩阵，并行处理其奇异值分解过程，从而提升运行速度。实验结果表明，该方法即使是串行处理，也使得大规模最小二乘奇异值分解的时间成本及空间成本大大降低；而并行处理在双机条件下加速比接近200％。