《计算机应用研究》|Application Research of Computers

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

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

免费全文下载 (已被下载 次)  
获取PDF全文
作者 吴文波,姚新宇,刘丽丽
机构 国防科学技术大学 a.信息系统与管理学院;b.机电工程与自动化学院,长沙 410073
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2014)11-3253-04
DOI 10.3969/j.issn.1001-3695.2014.11.013
摘要 大规模最小二乘问题求解中,直接进行奇异值分解会产生巨大的内存需求以及漫长的计算时间。为解决该问题,提出了一种基于迭代的并行处理方法。该方法利用奇异值分解降维的特性,通过迭代不断减小矩阵规模,直到可以直接使用奇异值分解求解。在迭代过程中,将矩阵分解为许多足够小的子矩阵,并行处理其奇异值分解过程,从而提升运行速度。实验结果表明,该方法即使是串行处理,也使得大规模最小二乘奇异值分解的时间成本及空间成本大大降低;而并行处理在双机条件下加速比接近200%。
关键词 最小二乘;奇异值分解;迭代;并行处理
基金项目 国家自然科学基金资助项目(61374185)
本文URL http://www.arocmag.com/article/01-2014-11-013.html
英文标题 Parallel processing for solving large-scale least square problem by singular value decomposition
作者英文名 WU Wen-bo, YAO Xin-yu, LIU Li-li
机构英文名 a. College of Information System & Management, b. College of Mechatronics Engineering & Automation, National University of Defence & Technology, Changsha 410073, China
英文摘要 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 problem even processed serially; and the speedup ratio of parallel processing in the circumstance of two nodes can be close to 200%.
英文关键词 least square problem; singular value decomposition; iteration; parallel processing
参考文献 查看稿件参考文献
  [1] 郭文斌. 奇异值分解及其在广义逆理论中的应用[M] . 北京:科学出版社, 2008.
[2] 王松桂, 陈敏, 陈立萍. 线性统计模型:线性回归与方差分析[M] . 北京:高等教育出版社, 1999.
[3] NIU S S, LJUNG L, BJORCK A. Decomposition methods for solving least-squares parameter estimation[J] . IEEE Trans on Signal Processing, 1996, 44(11):2847-2852.
[4] BJRCK A, YUAN Jin-yun. Preconditioners for least squares problems by LU factorization[J] . Electronic Trans on Numerical Analysis, 1999, 8:26-35.
[5] 曹新容, 黄联芬, 赵毅峰, 等. 一种最小二乘/奇异值分解算法[J] . 计算机工程, 2009, 35(16):278-279, 282.
[6] VOGEL C R, WADE J G. Iterative SVD-based methods for ill-posed problems[J] . SIAM Journal of Scientific Computing, 1994, 15(3):736-754.
[7] BECKA M, OKSA G, VAJTERSIC M. Dynamic ordering for a parallel block-Jacobi SVD algorithm[J] . Parallel Computing, 2002, 28(2):243-262.
[8] WEI Si-ming, LIN Zhou-chen. Accelerating iterations involving eigenvalue or singular value decomposition by block Lanczos with warm start[R] . Seattle:Microsoft Corp, 2010.
[9] 徐文华, 孙学栋. 奇异值分解求线性最小二乘解的理论分析[J] . 贵阳学院学报:自然科学版, 2009, 4(4):1-4.
[10] LEE S J, OUYANG Chen-sen. A neuro-fuzzy system modeling with self-constructing rule generation and hybrid SVD-based learning[J] . IEEE Trans on Fuzzy Systems, 2003, 11(3):341-353.
[11] Introduction to OpenMP:a directive-based API for parallel processing on shared-memory computers[EB/OL] . (2010-12-01)[2013-10-15] . http://scv. bu. edu/documentation/turials/OpenMP/.
[12] MPICH:high-performance portable MPI[EB/OL] . [2013-12-28] . http://www. mpich. org.
[13] SANDERSON C. Armadillo:an open source C++ linear algebra library for fast prototyping and computationally intensive experiments[R] . Sydney:NICTA, 2010.
[14] EIJKHOUT V. Introduction to high performace scientific computing[M] . Raleigh:Lulu. com, 2013.
收稿日期 2013/11/26
修回日期 2014/1/2
页码 3253-3256,3265
中图分类号 TP312
文献标志码 A