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

Parallel Algorithm of Block Bordered Linear Programming

作　　者：杨林峰[1] 李陶深[1] 李捷[2] 陈燕[1] 

机构地区：[1]广西大学,南宁530004 [2]广西职业技术学院计算机与电子信息工程系,南宁530226

出　　处：《计算机科学》2011年第9期204-207,共4页Computer Science

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

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]