We consider a class of incomplete preconditioners for sparse symmetric quasi-definite linear systems [3], which are known to admit a Cholesky LDL^T factorization (with D diagonal and indefinite). These specially structured systems arise when computing search directions in interior point methods for dual-regularized convex quadratic programs (QPs), and in the solution of regularized least squares.

Using the CSparse [1] package, we implement an incomplete sparse Cholesky factorization that allows the user to specify the amount of fill-in. The incomplete factorization proves to be an effective preconditioner for SYMMLQ [2] used within a convex QP code. We illustrate the performance of the preconditoner on a set of KKT matrices derived from QPs and regularized linear programs.

References
[1] T. A. Davis, Direct methods for sparse linear systems, vol. 2 of Fundamentals of Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006.
[2] C. C. Paige and M. A. Saunders, Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617–629.
[3] R. J. Vanderbei, Symmetric quasidefinite matrices, SIAM J. Optim., 5 (1995), pp. 100–113.