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

摘要：

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

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

所属期刊栏目：38

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：204-207