Sylvester’s identity and multistep integerpreserving Gaussian elimination
Author:
Erwin H. Bareiss
Journal:
Math. Comp. 22 (1968), 565578
MSC:
Primary 65.35
DOI:
https://doi.org/10.1090/S00255718196802268290
MathSciNet review:
0226829
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: A method is developed which permits integerpreserving 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 (singlestep) 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 twostep method. The method should also prove superior to the widely used fractionproducing Gaussian elimination when $A$ is nearly singular.

E. H. Bareiss, Multistep IntegerPreserving Gaussian Elimination, Argonne National Laboratory Report ANL7213, May, 1966.
E. H. Bareiss, The Root Cubing and the General Root Powering Methods for Finding the Zero of Polynomials, Argonne National Laboratory Report ANL7344, 1967.
J. Boothroyd, “Algorithm 290, linear equations, exact solutions $[F4]$,” Comm. ACM, v. 9, 1966, pp. 683–684.
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.
 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
 L. Fox, An introduction to numerical linear algebra, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436 B. S. Garbow, IntegerPreserving Gaussian Elimination, Program P158 (3600F), Applied Mathematics Division, Argonne National Laboratory, November 21, 1966. Gerhard Kowalewski, Einführung in die Determinantentheorie, Chelsea, New York, 1948.
 Mark Lotkin, Note on the method of contractants, Amer. Math. Monthly 66 (1959), 476–479. MR 105193, DOI https://doi.org/10.2307/2310629 R. H. Macmillan, “A new method for the numerical evaluation of determinants,” J. Roy. Aeronaut. Soc., v. 59, 1955, pp. 772ff.
 Thomas Muir, A treatise on the theory of determinants, Dover Publications, Inc., New York, 1960. Revised and enlarged by William H. Metzler. MR 0114826
 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
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