分块带边结构线性规划并行算法

作     者：杨林峰 李陶深 李捷 陈燕 YANG Lin-feng;LI Tao-shen;LI Jie;CHEN Yan

作者机构：广西大学南宁530004 广西职业技术学院计算机与电子信息工程系南宁530226 

基　　金：国家自然科学基金(60963022) 广西自然科学基金项目(桂科自0832056) 广西高校人才小高地建设创新团队资助计划(桂教人71号) 广西研究生教育创新计划资助项目(105930901022)资助 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2011年第38卷第9期

页      码：204-207页

摘      要：基于内点算法(Interior Point Method,IPM)框架,导出具有分块带边结构系数矩阵的线性规划(Linear Pro-gramming,LP)问题的简化和最简修正方程,并证明最简修正方程的对角分块具有正定性。结合正定矩阵的Cholesky分解和解耦技术设计了修正方程的并行求解方法,给出了LP的并行内点算法结构。集群环境下的数值实验表明,所提算法具有很好的加速比和可扩展性,适合求解大规模结构化LP问题。

主 题 词：线性规划 分块带边矩阵 并行算法 解耦 最简修正方程 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1002-137X.2011.09.047

馆 藏 号：203133973...