Computing a hybrid preconditioner approach to solve the linear systems arising from interior point methods for linear programming using the conjugate gradient method

In this work, iterative methods are used to solve the linear systems of equations arising from interior point methods. Since these systems of equations are very ill-conditioned near a solution, the design of specially tailored preconditioners is an important implementation issue. On the other hand, the early linear systems of equations do not present the same features and it is advisable to adopt hybrid preconditioners that begin as a generic preconditioner and adapt during the course of the iteration, becoming ever more specialized as convergence takes place. During the initial iterations, a controlled Cholesky factorization is used. As convergence takes place, a splitting, the splitting preconditioner is adopted. Its major advantage is its excellent behavior near a solution of the linear program. This desirable feature has a price. The preconditioner could be very expensive to compute. A careful implementation must be performed in order to achieve competitive results regarding both: speed and robustness. An effective implementation of the splitting preconditioner relies upon finding a suitable set of linearly independent columns to form a nonsingular matrix from the constraint matrix. Several strategies to help finding such set of columns are presented. Numerical experiments are carried out in order to illustrate the performance of the given strategies