Sylvester's identity and multistep integer-preserving Gaussian elimination

Author:
Erwin H. Bareiss

Journal:
Math. Comp. **22** (1968), 565-578

MSC:
Primary 65.35

DOI:
https://doi.org/10.1090/S0025-5718-1968-0226829-0

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, , such that the magnitudes of the coefficients in the transformed matrices are minimized, and 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 is nearly singular.

**[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 ,''*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)**

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