一个基于QR分解的并行原-对偶内点算法

应用科学学报 ›› 2004, Vol. 22 ›› Issue (4): 549-552.

一个基于QR分解的并行原-对偶内点算法

陈政洪, 郁松年

上海大学计算机工程与科学学院上海 200072

收稿日期:2003-07-10 修回日期:2003-09-15 出版日期:2004-12-31 发布日期:2004-12-31
作者简介:陈政洪(1975-),男,浙江绍兴人,硕士生.
基金资助:
上海市科委自然科学基金(00JC14052);上海市教委(网格技术-E研究院)资助项目

A Parallel Primal-Dual Interior Point Algorithm Based on the QR Decomposition

CHEN Zheng-hong, YU Song-nian

School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China

Received:2003-07-10 Revised:2003-09-15 Online:2004-12-31 Published:2004-12-31

摘要/Abstract

摘要： 首先介绍了原-对偶内点算法的主要计算步骤,阐明哪一步上可以进行并行化处理.接着介绍QR分解的理论,及如何利用QR分解并行求解线性方程组.最后提出了一种基于QR分解的并行内点算法,并给出了实验结果.

关键词: 并行, 原-对偶内点算法

Abstract: This paper first describes the steps involved in primal-dual interior point algorithm and explains which step in it can be parallelized. Next the theory of the QR decomposition is also detailed. It also points out how to use the QR decomposition to solve the linear simultaneous equations parallelly. In conclusion, it proposes a parallel primal-dual interior point algorithm based on the QR decomposition and lists some test results.

Key words: parallelism, primal-dual interior point algorithm

中图分类号:

TP301.6

陈政洪, 郁松年. 一个基于QR分解的并行原-对偶内点算法[J]. 应用科学学报, 2004, 22(4): 549-552.

CHEN Zheng-hong, YU Song-nian. A Parallel Primal-Dual Interior Point Algorithm Based on the QR Decomposition[J]. Journal of Applied Sciences, 2004, 22(4): 549-552.

[1]	张淑芬, 董岩岩, 陈学斌. 基于云计算平台Hadoop的HKM聚类算法设计研究[J]. 应用科学学报, 2018, 36(3): 524-534.
[2]	宋海峰, 陈广胜, 景维鹏, 杨巍巍. 基于(2D)²PCA的受限玻尔兹曼机图像分类算法及其并行化实现[J]. 应用科学学报, 2018, 36(3): 495-503.
[3]	张凌宇, 赵险峰. 一种基于嵌入列扩展的±1改进乘积隐写码[J]. 应用科学学报, 2016, 34(5): 575-584.
[4]	王龙1,2，杨俊安1,2，陈雷1,2，林伟3，刘辉1,2. 基于循环神经网络的汉语语言模型并行优化算法[J]. 应用科学学报, 2015, 33(3): 253-261.
[5]	赵旦峰，朱铁林，薛睿. 隐蔽通信中的Turbo 码并行译码[J]. 应用科学学报, 2012, 30(5): 461-465.
[6]	梁瑞宇1;3，赵力3，王青云2，奚吉1，张学武1. 数字助听器的并行梯度投影回声抵消[J]. 应用科学学报, 2012, 30(3): 256-262.
[7]	陈小敏，徐大专，虞湘宾. 不完全信道状态信息下的Turbo-BLAST系统及性能[J]. 应用科学学报, 2009, 27(3): 244-246.
[8]	张健;戎璐;胡宏林. 移动WiMAX系统级仿真建模与分布式实现[J]. 应用科学学报, 2008, 26(6): 556-561 .
[9]	吴悦;徐宝宇;唐立三;杨洪斌. SoC系统的并行性分析及划分[J]. 应用科学学报, 2008, 26(6): 632-637 .
[10]	李明;郑辉. 低信噪比下调制信号载波相位的迭代估计 [J]. 应用科学学报, 2008, 26(4): 358-0358 .
[11]	邱晓华, 沈连丰, 宋铁成, 沈克勤. 一种多路并行传输高速跳频通信系统[J]. 应用科学学报, 2005, 23(5): 461-466.
[12]	彭岳星, 吴镇扬, 王维新, 刘陈. 频选瑞利快衰落信道下的迭代多用户检测算法[J]. 应用科学学报, 2005, 23(3): 245-250.
[13]	李胜利, 唐维, 石柯, 程斌, 蒙廷友. 高可用并行文件系统的分布式元数据管理[J]. 应用科学学报, 2005, 23(3): 297-299.
[14]	韩玉兵, 吴乐南. 基于改进Paik型Hopfield网络的图像复原[J]. 应用科学学报, 2005, 23(2): 126-130.
[15]	李晋, 徐晓东, 姜明, 尤肖虎. PCGC码低复杂度译码算法的研究[J]. 应用科学学报, 2005, 23(2): 140-143.