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 stateoftheart 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 primaldual 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.65097 Gondzio, 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, JeanPhilippe 
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 (90XX) 
1  Numerical analysis (65XX) 
1  Mathematics education (97XX) 