Remote Access Mathematics of Computation
Green Open Access

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. Vol. II: Systèmes de Plusieurs Équations. Valeurs Propres des Matrices, Masson et Cie, Paris, 1961. MR 24 #B1754. MR 0135709 (24:B1754)
  • [6] L. Fox, An Introduction to Numerical Linear Algebra, Clarendon Press, Oxford, 1964. MR 29 #1733. 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, v. 66, 1959, pp. 476-479. MR 21 #3936. 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, The Theory of Determinants in Historical Order of Development, four volumes bound as two (I, 1693-1841; II, 1841-1860; III, 1861-1880; IV, 1880-1900), Dover, New York, 1960; Contributions to the History of Determinants 1900-1920, Blackie & Son, London, 1930 & 1950. MR 0114826 (22:5644)
  • [12] J. B. Rosser, ``A method of computing exact inverses of matrices with integer coefficients,'' J. Res. Nat. Bur. Standards Sect. B, v. 49, 1952, pp. 349-358. MR 14, 1128. 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

Article copyright: © Copyright 1968 American Mathematical Society

American Mathematical Society