Retreat 2006 SCHEDULE     Retreat 2006 PICTURES

Timothy Rees
Guest M.Sc. Student, Department of Computer Science

A Preconditioner for Linear Systems Arising in Linear and Quadratic Programming

We investigate the application of a class of preconditioners to the problem of solving the linear systems arising from primal-dual interior point methods in linear and quadratic programming (LP and QP). The preconditioners have the attractive property of improved eigenvalue clustering with increased singularity of the (1,1) block of the saddle-point matrix. We analyze spectral properties of the preconditioned matrix utilizing projections onto the null space of the constraint matrix. We then present a practical application of the preconditioners and study their performance on LP and QP problems from the NETLIB and QPS test suites.

Tim Rees