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

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. 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**, https://doi.org/10.2307/2310629**[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**

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