zbMATH — the first resource for mathematics

Fast Cholesky factorization for interior point methods of linear programming. (English) Zbl 0879.90143
Summary: Every iteration of an interior point method of large scale linear programming requires computing at least one orthogonal projection. In practice, Cholesky decomposition seems to be the most efficient and sufficiently stable method. We studied the ‘column oriented’ or ‘left looking’ sparse variant of the Cholesky decomposition, which is a very popular method in large scale optimization. We show some techniques such as using supernodes and loop unrolling for improving the speed of computation. We show numerical results on a wide variety of large scale, real-life linear programming problems.

90C05 Linear programming
90C06 Large-scale problems in mathematical programming
65K05 Numerical mathematical programming methods
PDF BibTeX Cite
Full Text: DOI
[1] Gonzaga, C.G., Path following methods for linear programming, SIAM review, 34, 2, 167-227, (1992) · Zbl 0763.90063
[2] George, A.; Liu, J.W.H., Computer solution of large scale positive definite systems, (1981), Prentice-Hall Englewood Cliffs, NJ
[3] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., The interaction of algorithms and architectures for interior point method, (), 190-205 · Zbl 0814.90080
[4] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., Interior point methods for linear programming: computational state of the art, ORSA journal on computing, 6, 2, 1-14, (1994) · Zbl 0798.90100
[5] Rothberg, E.; Gupta, A., Efficient sparse matrix factorization on high-performance workstations—exploiting the memory hiearchy, ACM transactions on mathematical software, 17, 3, 313-334, (1991) · Zbl 0900.65066
[6] Duff, I.S.; Erisman, A.M.; Reid, J.K., Direct methods for sparse matrices, (1967), Calderon Press Oxford · Zbl 0666.65024
[7] Ashcraft, C.C.; Grimes, R.G.; Lewis, J.G.; Peyton, B.W.; Simon, H.D., Recent progress in sparse matrix methods for large linear systems, Int. J. supercomput. appl., 1, 4, 10-30, (1987)
[8] Esmond, N.G.; Peyton, B.W., A supernodal Cholesky factorization algorithm for shared-memory multi-processors, SIAM journal on scientific computing, 14, 2, 761-769, (1993) · Zbl 0785.65014
[9] Gay, D.M., Electronic mail distribution of linear programming test problems, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.