摘要
基于内点算法(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.
出处
《计算机科学》
CSCD
北大核心
2011年第9期204-207,共4页
Computer Science
基金
国家自然科学基金(60963022)
广西自然科学基金项目(桂科自0832056)
广西高校人才小高地建设创新团队资助计划(桂教人[2007]71号)
广西研究生教育创新计划资助项目(105930901022)资助
关键词
线性规划
分块带边矩阵
并行算法
解耦
最简修正方程
Linear programming
Block bordered matrix
Parallel algorithm
Decoupling
Simplest correction equation
