×
Reid, J. K.

A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases. (English) Zbl 0492.90050

Math. Program. 24, 55-69 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0492.90050

Cited in 47 Documents

MSC:

90C06 Large-scale problems in mathematical programming
65K05 Numerical mathematical programming methods
90C05 Linear programming

Keywords:

test results; decompositions; updating lp basis factorizations; simplex method; implementation; Bartels and Golub algorithm; sparse matrices; Forrest and Fomlin algorithm; computational comparison

Citations:

Zbl 0282.90027

Software:

XMP
PDF BibTeX XML Cite
\textit{J. K. Reid}, Math. Program. 24, 55--69 (1982; Zbl 0492.90050)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] R.H. Bartels, ”A stabilization of the simplex method”,Numerische Mathematik 16 (1971) 414–434. · Zbl 0197.43305
[2] E.M.L. Beale, ”Sparseness in linear programming”, in: J.K. Reid, ed.,Large sparse sets of linear equations (Academic Press, London, 1971) pp. 1–15.
[3] A.R. Curtis and J.K. Reid, ”On the automatic scaling of matrices for Gaussian elimination”,Journal of the Institute of Mathematics and its Applications 10 (1972) 118–124. · Zbl 0249.65026
[4] I.S. Duff and J.K. Reid, ”A comparison of sparsity orderings for obtaining a pivotal sequence in Gaussian elimination”,Journal of the Institute of Mathematics and its Applications 14 (1974) 281–291. · Zbl 0308.65021
[5] B. Ford, ed., ”Parameterization of the environment for transportable numerical software”,ACM Transactions on Mathematical Software 4 (1978) 100–103.
[6] J.J.H. Forrest and J.A. Tomlin, ”Updating triangular factors of the basis to maintain sparsity in the product form simplex method”,Mathematical Programming 2 (1972) 263–278. · Zbl 0288.90048
[7] D.M. Gay, ”On combining the schemes of Reid and Saunders for sparse LP bases”, in: I.S. Duff and G.W. Stewart, eds.,Sparse matrix proceedings 1978 (SIAM, Philadelphia, PA, 1979) pp. 313–334.
[8] D. Goldfarb, ”On the Bartels–Golub decomposition for linear programming bases”,Mathematical Programming 13 (1977) 272–279. · Zbl 0379.90070
[9] F.G. Gustavson, ”Some basic techniques for solving sparse systems of linear equations, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum Press, New York, 1972) pp. 41–52.
[10] E. Hellerman and D.C. Rarick, ”Reinversion with the preassigned pivot procedure”,Mathematical Programming 1 (1971) 195–216. · Zbl 0246.65022
[11] R.D. McBride, ”A bump triangular dynamic factorization algorithm for the simplex method”,Mathematical Programming 18 (1980) 49–61. · Zbl 0428.90039
[12] H.M. Markowitz, ”The elimination form of the inverse and its applications to linear programming”,Management Science 3 (1957) 255–269. · Zbl 0995.90592
[13] R.E. Marsten, ”The design of the XMP linear programming library”,ACM Transactions on Mathematical Software (1981).
[14] W. Orchard-Hays,Advanced linear-programming computing techniques (McGraw-Hill, New York, 1968). · Zbl 0995.90595
[15] A.F. Perold, ”A degeneracy exploiting LU factorization for the simplex method”,Mathematical Programming 19 (1980) 239–254. · Zbl 0442.90054
[16] J.K. Reid, ”A note on the stability of Gaussian elimination”,Journal of the Institute of Mathematics and its Applications 8 (1971) 374–375. · Zbl 0229.65030
[17] J.K. Reid, ”Sparse linear programming using the Bartels–Golub decomposition”, verbal presentation at VIII International Symposium on Mathematical Programming, Stanford, CA (1973).
[18] J.K. Reid, ”Fortran subroutines for handling sparse linear programming bases”, Report AERER.8269, Harwell (1976).
[19] M.A. Saunders, ”Large-scale linear programming using the Cholesky factorization”, Report STAN-CS-72-252, Department of Computer Science, Stanford University, Stanford, CA (1972).
[20] M.A. Saunders, ”The complexity of LU updating in the simplex method”, in: R.S. Anderssen and R.P. Brent, eds.,The complexity of computational problem solving (University Press, Queensland, 1976) pp. 214–230.
[21] J.A. Tomlin, ”Pivoting for size and sparsity in linear programming inversion routines”,Journal of the Institute of Mathematics and its Applications 10 (1972) 289–295. · Zbl 0249.90039
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.