article

Free access

A mathematical programming updating method using modified Givens transformations and applied to LP problems

Authors:

Richard J. Hanson,

John A. WisniewskiAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 4

Pages 245 - 251

https://doi.org/10.1145/359094.359100

Published: 01 April 1979 Publication History

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.

Digital Library

[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.

Digital Library

[4]

Dahl, O.-J., Dijkstra, E.W., and Hoare, C.A.R. Structured Programming. Academic Press, New York, 1972.

Digital Library

[5]

Dantzig, G.B. Linear Programming and Extensions. Princeton U. Press, Princeton, New Jersey, 1963.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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.

Digital Library

[23]

Saunders, M.A. Large-scale linear programming using the Cholesky factorization. Rep. STAN-CS-72-252, Stanford U., Stanford, Calif., 1975.

Digital Library

[24]

Wilkinson, J.H. The Algebraic Eigenvalue Problem. Oxford U. Press, 1965.

Digital Library

Cited By

Kao CSmith W(1999)Sensitivity of a cloud parameterization package in the National Center for Atmospheric Research Community Climate ModelJournal of Geophysical Research: Atmospheres10.1029/1999JD900079104:D10(11961-11983)Online publication date: 1-May-1999
https://doi.org/10.1029/1999JD900079
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
https://doi.org/10.1016/0024-3795(88)90197-8

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

cover image Communications of the ACM

Communications of the ACM Volume 22, Issue 4

April 1979

46 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359094

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

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

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)15

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kao CSmith W(1999)Sensitivity of a cloud parameterization package in the National Center for Atmospheric Research Community Climate ModelJournal of Geophysical Research: Atmospheres10.1029/1999JD900079104:D10(11961-11983)Online publication date: 1-May-1999
https://doi.org/10.1029/1999JD900079
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
https://doi.org/10.1016/0024-3795(88)90197-8

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents