CHFACT 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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Implementing Cholesky factorization for interior point methods of linear programming. Zbl 0819.65097Gondzio, J. 1993 all top 5 Cited by 7 Authors 4 Gondzio, Jacek 1 Breedveld, Sebastiaan 1 Heijmen, Ben 1 Makowski, Marek S. 1 Sarkissian, Robert 1 van den Berg, Bas 1 Vial, Jean-Philippe Cited in 3 Serials 3 European Journal of Operational Research 1 Optimization 1 Computational Optimization and Applications Cited in 3 Fields 5 Operations research, mathematical programming (90-XX) 1 Numerical analysis (65-XX) 1 Mathematics education (97-XX) Citations by Year