PCG techniques for interior point algorithms

In many engineering applications, very large, sparse linear programs (LPs) arise. Fast interior point algorithms for solving LPs are currently gaining popularity over traditional simplex methods. The bottleneck step of the interior point method is the solution of the normal equations or of an equivalent “augmented” system at each iteration. The current work examines the effectiveness of the preconditioned conjugate gradient (PCG) method for the symmetric positive definite normal equations. In addition, we discuss the use of a PCG variant for the indefinite augmented equations. Although the methods can be applied to LPs from different application areas, we focus an problems from VLSI layout optimization