| 分块带边结构线性规划并行算法 |
| |
| 引用本文： | 杨林峰,李陶深,李捷,陈燕.分块带边结构线性规划并行算法[J].计算机科学,2011,38(9):204-207. |
| |
| 作者姓名： | 杨林峰 李陶深 李捷 陈燕 |
| |
| 作者单位： | (广西大学 南宁 530004);(广西职业技术学院计算机与电子信息工程系 南宁 530226) |
| |
| 基金项目： | 本文受国家白然科学基金(60963022) ,广西自然科学基金项目(桂科自0832066) ,广西高校人才小高地建设创新团队资助计划(桂教人[2007习71号),J‘一西研究生教育创新计划资助项目(105930901022)资助。 |
| |
| 摘 要： | 基于内点算法((Interior Point Method,IPM)框架，导出具有分块带边结构系数矩阵的线性规划(Linear Programming, I_P)问题的简化和最简修正方程，并证明最简修正方程的对角分块具有正定性。结合正定矩阵的Cholcsky分解和解藕技术设计了修正方程的并行求解方法，给出了LP的并行内点算法结构。集群环境下的数值实验表明，所提算法具有很好的加速比和可扩展性，适合求解大规模结构化工尹问题。
|
| 关 键 词： | 线性规划，分块带边矩阵，并行算法，解藕，最简修正方程 |
Parallel Algorithm of Block Bordered Linear Programming |
| |
| YANG lin-feng,LI Tao-sheng,LI Jie,CHEN Yan.Parallel Algorithm of Block Bordered Linear Programming[J].Computer Science,2011,38(9):204-207. |
| |
| Authors: | YANG lin-feng LI Tao-sheng LI Jie CHEN Yan |
| |
| Affiliation: | (Guangxi University, Manning 530004, China);(Department of Computer,Electronics and Information Engineering,Uuangxi Polytechnic,Nanning 530226,China) |
| |
| Abstract: | This paper presented the simpler and simplest correction equation of linear programming(LP) with block bordered coefficient matrix based on the framework of interior point method(IPM). And the diagonal sulrmatrix in the simplest correction equation was proved to be symmetric positive definite. Parallel IPM algorithm for LP was presented after a parallel solver for correction equation was proposed by integrating decoupling and Cholesky factorization of symmetric positive definite matrix The simulations in the cluster show that the proposed method is very promising for large scale LP problems due to its excellent speed up and scalability. |
| |
| Keywords: | Linear programming Block bordered matrix Parallel algorithm Decoupling Simplest correction equation |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
