Using incomplete indefinite $LDL^T$ preconditioning for inexact interior point methods for linear programming
This work addresses the high computational cost and memory requirements of solving linear systems in interior point methods for linear programming, which is a bottleneck for large-scale problems.
The paper implements an interior point method for linear programming that avoids forming the normal equation matrix N, instead solving reduced KKT systems iteratively with low accuracy using SQMR and an indefinite multilevel preconditioner. Preliminary numerical results are encouraging.
Most linear algebra kernels in interior point methods for linear programming require the solution of linear systems of equation with the matrix $N = A^TD^{-1}A$ (or $AD^{-1}A^T$), where $A$ denotes the constraint matrix of the linear program. This matrix $N$ arises from the reduced KKT system by block elimination. If the number of non-zeros in $N$ or in its Cholesky factorization $N= LL^T$ is very large, the computational cost and memory requirement to solve the linear systems of equations with $N$ may be prohibitively large. In this work we implement an interior point method described by R. Freund and F. Jarre. Forming the normal equation matrix $N$ is avoided altogether and we work with the reduced KKT system instead. We solve the linear systems for the Newton directions iteratively only to low accuracy using SQMR and an indefinite multilevel preconditioner. Preliminary numerical results are encouraging.