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