Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

Sylvester's identity and multistep integer-preserving Gaussian elimination


Author: Erwin H. Bareiss
Journal: Math. Comp. 22 (1968), 565-578
MSC: Primary 65.35
MathSciNet review: 0226829
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A method is developed which permits integer-preserving elimination in systems of linear equations, $ AX = B$, such that $ (a)$ the magnitudes of the coefficients in the transformed matrices are minimized, and $ (b)$ the computational efficiency is considerably increased in comparison with the corresponding ordinary (single-step) Gaussian elimination. The algorithms presented can also be used for the efficient evaluation of determinants and their leading minors. Explicit algorithms and flow charts are given for the two-step method. The method should also prove superior to the widely used fraction-producing Gaussian elimination when $ A$ is nearly singular.


References [Enhancements On Off] (What's this?)

  • [1] E. H. Bareiss, Multistep Integer-Preserving Gaussian Elimination, Argonne National Laboratory Report ANL-7213, May, 1966.
  • [2] E. H. Bareiss, The Root Cubing and the General Root Powering Methods for Finding the Zero of Polynomials, Argonne National Laboratory Report ANL-7344, 1967.
  • [3] J. Boothroyd, ``Algorithm 290, linear equations, exact solutions $ [F4]$,'' Comm. ACM, v. 9, 1966, pp. 683-684.
  • [4] C. L. Dodgson, ``Condensation of determinants, being a new and brief method for computing their arithmetic values,'' Proc. Roy. Soc. Ser. A, v. 15, 1866, pp. 150-155.
  • [5] E. Durand, Solutions numériques des équations algébriques. Tome II: Systèmes de plusieurs équations. Valeurs propres des matrices, Masson et Cie, Éditeurs, Paris, 1961 (French). MR 0135709 (24 #B1754)
  • [6] L. Fox, An introduction to numerical linear algebra, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436 (29 #1733)
  • [7] B. S. Garbow, Integer-Preserving Gaussian Elimination, Program P-158 (3600F), Applied Mathematics Division, Argonne National Laboratory, November 21, 1966.
  • [8] Gerhard Kowalewski, Einführung in die Determinantentheorie, Chelsea, New York, 1948.
  • [9] Mark Lotkin, Note on the method of contractants, Amer. Math. Monthly 66 (1959), 476–479. MR 0105193 (21 #3936)
  • [10] R. H. Macmillan, ``A new method for the numerical evaluation of determinants,'' J. Roy. Aeronaut. Soc., v. 59, 1955, pp. 772ff.
  • [11] Thomas Muir, A treatise on the theory of determinants, Revised and enlarged by William H. Metzler, Dover Publications Inc., New York, 1960. MR 0114826 (22 #5644)
  • [12] J. Barkley Rosser, A method of computing exact inverses of matrices with integer coefficients, J. Research Nat. Bur. Standards 49 (1952), 349–358. MR 0055796 (14,1128a)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65.35

Retrieve articles in all journals with MSC: 65.35


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1968-0226829-0
PII: S 0025-5718(1968)0226829-0
Article copyright: © Copyright 1968 American Mathematical Society