Cited By
View all- Ogryczak W(1988)The simplex method is not always well behavedLinear Algebra and its Applications10.1016/0024-3795(88)90197-8109(41-57)Online publication date: Oct-1988
A mathematical programming updating method using modified Givens transformations and applied to LP problems
Abstract
An efficient and numerically stable method is presented for the problem of updating an orthogonal decomposition of a matrix of column (or row) vectors. The fundamental idea is to add a column (or row) analogous to adding an additional row of data in a linear least squares problem. A column (or row) is dropped by a formal scaling with the imaginary unit, √-1, followed by least squares addition of the column (or row). The elimination process for the procedure is successive application of the Givens transformation in modified (more efficient) form. These ideas are illustrated with an implementation of the revised simplex method. The algorithm is a general purpose one that does not account for any particular structure or sparsity in the equations. Some suggested computational tests for determining signs of various controlling parameters in the revised simplex algorithm are mentioned. A simple means of constructing test cases and some sample computing times are presented.
References
[1]
Aird, T., and Lynch, R. Computable accurate upper and lower error bounds for approximate solutions of linear algebraic systems. Trans. Math. Software l, 3 (1975), 217-231.
[2]
Bartels, R.H, Stoer, J., and Zenger, Ch. A realization of the simplex method based on triangular decompositions. In Linear Algebra 2, Springer-Verlag, New York, 1971.
[3]
Bland, R.G. New finite pivoting rules for the simplex method. Math. Opns. Res. 2 (1977), 103-107.
[4]
Dahl, O.-J., Dijkstra, E.W., and Hoare, C.A.R. Structured Programming. Academic Press, New York, 1972.
[5]
Dantzig, G.B. Linear Programming and Extensions. Princeton U. Press, Princeton, New Jersey, 1963.
[6]
Gale, D. The Theory of Linear Economic Models. McGraw-Hill, New York, 1960.
[7]
Gentleman, W.M. Least squares computations by Givens transformations without square roots. J. Inst. Math. Appl. 12 (1973), 329-336.
[8]
Gill, P.E., and Murray, W. A numerically stable form of the simplex algorithm. Linear Algebra and Appl. 7 (1973), 99-138.
[9]
Gill, P.E., Golub, G.H., Murray, W., and Saunders, M.A. Methods for modifying matrix factorization. Math. Comp. 28, 126 (April 1974), 505-535.
[10]
Gill, P.E., Murray, W., and Saunders, M.A. Methods for computing and modifying the LDV factors of a matrix. Math. Comp. 29, 132 (October 1975), 1051-1077.
[11]
Goldfarb, D., and Reid, J. A practicable steepest edge simplex algorithm. AERE Harwell Rep. CSSI9, Oxfordshire, England, July 1975.
[12]
Hadley, G. Linear Programming. Addison-Wesley, Reading, Mass., 1962.
[13]
Hammerling, S. A note on modifications to the Givens plane rotation. J. Inst. Math. Appl. 13 (1974), 215-218.
[14]
Hanson, R.J., and Wisniewski, J.A. A revised simplex code for LP problems using orthogonal decomposition--A user's guide. Sandia Lab. Tech. Rep. SAND78-2322, Albuquerque, New Mexico, 1979.
[15]
Hopper, M.J. Harwell subroutine library, A catalogue of subroutines, Suppl. 2, 1973; AERE-R-7477, Suppl. 2, August 1977.
[16]
IMSL Library 1, Ed. 6. Houston, Texas.
[17]
Kowalik, J., and Kumar, S. Fast Givens transformations applied to the homogeneous optimization method. Appl. Math. and Comp. 4 (1978), pp. 239-252.
[18]
Lawson, C. On the discovery and description of mathematical programming algorithms. Proc. Dundee Biennial Conf. Numerical Analysis, July 1-4, 1975; Lecture Notes in Mathematics 506, Springer-Verlag, pp. 157-165.
[19]
Lawson, C., and Hanson, R. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
[20]
Lawson, C., Hanson, R., Krogh, F., and Kinkaid, D. Basic linear algebra subprograms for Fortran usage. Sandia Lab. Tech. Rep. SAND77-0898, Albuquerque, New Mexico, 1978 (submitted to Trans. Math. Software, June 1977).
[21]
Orchard-Hays, W. Advanced Linear-Programming Computing Techniques. McGraw-Hill, New York, 1968.
[22]
Rosen, J.B., and Suzuki, S. Construction of nonlinear programming test problems. Comm. A CM 8, 2 (Feb. 1965), 113.
[23]
Saunders, M.A. Large-scale linear programming using the Cholesky factorization. Rep. STAN-CS-72-252, Stanford U., Stanford, Calif., 1975.
[24]
Wilkinson, J.H. The Algebraic Eigenvalue Problem. Oxford U. Press, 1965.
- A mathematical programming updating method using modified Givens transformations and applied to LP problems
Recommendations
Modified incomplete orthogonal factorization methods using Givens rotations
We present a class of new preconditioners based on the incomplete Givens orthogonalization (IGO) methods for solving large sparse systems of linear equations. In the new methods, instead of dropping entries and accepting fill-ins according to the ...
Practical Use of Some Krylov Subspace Methods for Solving Indefinite and Nonsymmetric Linear Systems
The main purpose of this paper is to develop stable versions of some Krylov subspace methods for solving linear systems of equations $Ax = b$. As in the case of Paige and Saunders's SYMMLQ [SIAM J. Numer. Anal., 12 (1975), pp. 617–624], our algorithms ...
A fast method for solving a class of tridiagonal linear systems
The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the LU decomposition of the coefficient matrix rapidly converge to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 1979
46 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/359094
- Editor:
- Robert L. Ashenhurst
Copyright © 1979 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 April 1979
Published in CACM Volume 22, Issue 4
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 539Total Downloads
- Downloads (Last 12 months)71
- Downloads (Last 6 weeks)11
Reflects downloads up to 15 Feb 2025
Other Metrics
Citations
Cited By
View all- Ogryczak W(1988)The simplex method is not always well behavedLinear Algebra and its Applications10.1016/0024-3795(88)90197-8109(41-57)Online publication date: Oct-1988
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in