swMATH ID: 30976
Software Authors: Gondzio, J.
Description: Implementing Cholesky factorization for interior point methods of linear programming. Every iteration of an interior point method of large scale linear programming requires computing at least one orthogonal projection of the objective function gradient onto the null space of a linear operator defined by the problem constraint matrix A. The orthogonal projection itself is in turn dominated by the inversion of the symmetric matrix of form AçA T, where ç is a diagonal weighting matrix. In this paper several specific issues of implementation of the Cholesky factorization that can be applied for solving such equations are discussed. The code called CHFACT being the result of this work is shown to produce comparably sparse factors as the state-of-the-art implementation of the Cholesky decomposition of George and Liu (1981). It has been used for computing projections in an efficient implementation of a higher order primal-dual interior point method of Altman and Gondzio (1992a, b). Although primary aim of developing CHFACT was to include it into an LP optimizer, the code may equally well be used to solve general large sparse positive definite systems arising in different applications
Homepage: https://www.tandfonline.com/doi/abs/10.1080/02331939308843876
Keywords: interior point method; large scale linear programming; orthogonal projection; Cholesky factorization; large sparse positive definite systems
Related Software: HOPDM; QHOPDM; MA27; symrcm; IPMLO; Netlib; TROTS; CUTEst; Scotch; LOQO; LSQR; OSL; MINOS
Cited in: 5 Publications

Citations by Year