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

《大规模最小二乘奇异值分解的并行处理方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第3l卷第11期计算机应用研究V01．31No．112014年11月ApplicationResearchofComputersNOV．2014大规模最小二乘奇异值分解的并行处理方法吴文波，姚新宇，刘丽丽(国防科学技术大学a．信息系统与管理学院；b．机电工程与自动化学院，长沙410073)摘要：大规模最小二乘问题求解中，直接进行奇异值分解会产生巨大的内存需求以及漫长的计算时间。为解决该问题，提出了一种基于迭代的并行处理方法。该方法利用奇畀值分解降维的特性，通过迭代不断减小矩阵规模，直到可以直接使用奇异值分解求解。在迭代过程中，将矩阵分解为许多足够小

2、的子矩阵，并行处理其奇异值分解过程。从而提升运行速度。实验结果表明，该方法即使是串行处理，也使得大规模最小二乘奇异值分解的时间成本及空间成本大大降低；而并行处理在双机条件下加速比接近200％。关键词：最小二乘；奇异值分解；迭代；并行处理中图分类号：TP312文献标志码：A文章编号：1001—3695(2014)11—3253—04doi：10．3969／j．issn．1001．3695．2014．11．013Parallelprocessingforsolvinglarge—scaleleastsquareproblembysingularvalu

3、edecompositionWUWen—bo．YAOXin—yu．LIULi—li(a．CollegeofInformationS~tem＆Management，b．CollegeofMechatronicsEngineering＆Automation，NationalUniversityofDefence&TechnologY，Changsha410073，China)Abstract：Forlarge—scaleleastsquareproblem，applyingSVDdirectlyonthematrixrequiredhugememory

4、demanding，anditwastimeconsuming，thispaperproposedaniterationbasedparallelprocessingmethodforsolvingthisproblem．ThismethodtookadvantageofmatrixdimensiondecreasingfeatureofSVD，andthematrixbecamesmallerbyiteration，untilthematrixwassmallenoughwhichcouldbesolvedbySVDdirectly．Inthei

5、teration，itdividedthematrixintolotsofsubmatircesthatweresmallenoughtobesolvedbySVD，theycouldbeprocessedinparallel，SOthatitimprovedtheprocessingspeed．Experimentresultsshowthat，theproposedmethodcangreatlydecreasetherequirementsintimeandspaceofsolvinglarge—scaleleastsquareprob·le

6、mevenprocessedserially；andthespeedupratioofparallelprocessinginthecircumstanceoftwonodescanbecloseto200％．Keywords：leastsquareproblem；singularvaluedecomposition；iteration；parallelprocessing算机并行化的发展，人们自然而然地想到并行处理的方法，提0引言出了许多基于并行与迭代的算法，如Vogel等人提出的基于Lanczos的算法，Becka等人提出的并行双端块雅克比(p

7、aral-在数据拟合、参数估计和系统辨识等控制理论工程领域的实际问题中，多元线性回归分析是应用最为广泛的模型之一。leltwo—sideblock-Jacobi)算法，以及Wei等人提出的块Lanc—很多情况下，实际问题得到的线性方程组往往是无解或矛盾ZOS方法等。但是这些方法都是对SVD计算本身的改进。的，本身不能找到满足条件的参数向量，只能寻求最小二乘解，通过对SVD方法的分析，可以发现其核心思想在于降维即寻找回归参数向量的估计，使得偏差向量的F一范数达到最处理，使得高维矩阵转换为低维矩阵，从而更加易于处理计算。小，该方法称为回归参数向量的最d

8、~---乘估计问题⋯。因此，本文利用该特性，通过迭代的方法不断减小设计矩阵规求解最小二乘问题的方法有很多，如基于微积分极值