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

Abstract: 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 sulrmatrix 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.

Key words: Linear programming, Block bordered matrix, Parallel algorithm, Decoupling, Simplest correction equation