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. Tome II: Systèmes de plusieurs équations. Valeurs propres des matrices, Masson et Cie, Éditeurs, Paris, 1961 (French). MR 0135709
  • [6] L. Fox, An introduction to numerical linear algebra, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436
  • [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
  • [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
  • [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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65.35

Retrieve articles in all journals with MSC: 65.35


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1968-0226829-0
Article copyright: © Copyright 1968 American Mathematical Society