Sylvester’s identity and multistep integerpreserving Gaussian elimination
HTML articles powered by AMS MathViewer
 by Erwin H. Bareiss PDF
 Math. Comp. 22 (1968), 565578 Request permission
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.References

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 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, DOI 10.6028/jres.049.036
Additional Information
 © Copyright 1968 American Mathematical Society
 Journal: Math. Comp. 22 (1968), 565578
 MSC: Primary 65.35
 DOI: https://doi.org/10.1090/S00255718196802268290
 MathSciNet review: 0226829