Abstract
A compact and flexible updating procedure using matrix augmentation is developed. It is shown that the representation of the updated inverse does not grow monotonically in size, and may actually decrease during certain simplex iterations. Angular structures, such as GUB, are handled naturally within the partitioning framework, and require no modifications of the simplex method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.H. Bartels and G.H. Golub, “The simplex method of linear programming using LU decomposition”,Communications of the Association for Computing Machinery 12 (1969) 266–268.
J. Bisschop and A. Meeraus, “A recursive form of the inverse of general sparse matrices”, DRC technical note #1, Development Research Center, World Bank (Washington, DC, 1976).
G.B. Dantzig and R.M. Van Slyke, “Generalized upper bounding techniques for linear programming”,Journal of Computer and Systems Sciences 1 (1967) 213–226.
G. Forsythe and C. Moler,Computer solution of linear algebraic systems (Prentice-Hall, Englewood Cliffs, NJ, 1967).
P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, “Methods for modifying matrix factorizations”,Mathematics of Computation 28 (1974) 505–535.
D. Goldfarb, “On the Bartels—Golub decomposition for linear programming bases”, Report CSS, Atomic Energy Research Establishment (Harwell, Didcot, Oxfordshire, 1975).
E. Hellerman and D. Rarick, “Reinversion with the preassigned pivot procedure”,Mathematical Programming 2 (1971) 195–216.
R.N. Kaul, “An extension of generalized upper bounding techniques for linear programming”, ORC 65-27, Operations Research Center, University of California at Berkeley (1965).
G. Kron,Diakoptics (MacDonald, London, 1956).
L.S. Lasdon,Optimization theory for large systems (MacMillan Company, New York, 1970).
J.K. Reid, “A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases”, Report CSS, Atomic Energy Research Establishment (Harwell, Didcot, Oxfordshire, 1975).
D.J. Rose and J.R. Bunch, “The role of partitioning in the numerical solution of sparse systems”, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum Press, New York, 1972).
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, 1972).
J. Sherman and W.J. Morrison, “Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix”,Annals of Mathematical Statistics 20 (1949) 621.
J.A. Tomlin, “Modifying triangular factors of the basis in the simplex method”, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum Press, New York, 1972).
J.A. Tomlin, “An accuracy test for updating triangular factors”,Mathematical Programming Study 4 (1975) 142–145.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bisschop, J., Meeraus, A. Matrix augmentation and partitioning in the updating of the basis inverse. Mathematical Programming 13, 241–254 (1977). https://doi.org/10.1007/BF01584341
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584341