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

• 作者: 李捷 李陶深 杨林峰 陈燕
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 线性规划 分块带边矩阵 并行算法 解耦 最简修正方程
• 年，卷（期）: 2011,（9）
• 所属期刊栏目: 人工智能
• 页码范围: 204-207
• 分类号: TP301.6
• 字数: 2968字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2011.09.047

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李陶深		394	2640	25.0	36.0
2	陈燕		77	344	9.0	15.0
3	李捷	广西职业技术学院计算机与电子信息工程系	12	61	4.0	7.0
4	杨林峰		19	108	6.0	10.0