Sylvester's identity and multistep integerpreserving Gaussian elimination
Author:
Erwin H. Bareiss
Journal:
Math. Comp. 22 (1968), 565578
MSC:
Primary 65.35
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, , 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 (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 is nearly singular.
 [1]
E. H. Bareiss, Multistep IntegerPreserving Gaussian Elimination, Argonne National Laboratory Report ANL7213, 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 ANL7344, 1967.
 [3]
J. Boothroyd, ``Algorithm 290, linear equations, exact solutions ,'' Comm. ACM, v. 9, 1966, pp. 683684.
 [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. 150155.
 [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
(24 #B1754)
 [6]
L.
Fox, An introduction to numerical linear algebra, Monographs
on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436
(29 #1733)
 [7]
B. S. Garbow, IntegerPreserving Gaussian Elimination, Program P158 (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
(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, A treatise on the theory of determinants, Revised and
enlarged by William H. Metzler, Dover Publications Inc., New York, 1960. MR 0114826
(22 #5644)
 [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
(14,1128a)
 [1]
 E. H. Bareiss, Multistep IntegerPreserving Gaussian Elimination, Argonne National Laboratory Report ANL7213, 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 ANL7344, 1967.
 [3]
 J. Boothroyd, ``Algorithm 290, linear equations, exact solutions ,'' Comm. ACM, v. 9, 1966, pp. 683684.
 [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. 150155.
 [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, IntegerPreserving Gaussian Elimination, Program P158 (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. 476479. 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, 16931841; II, 18411860; III, 18611880; IV, 18801900), Dover, New York, 1960; Contributions to the History of Determinants 19001920, 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. 349358. MR 14, 1128. MR 0055796 (14:1128a)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65.35
Retrieve articles in all journals
with MSC:
65.35
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718196802268290
PII:
S 00255718(1968)02268290
Article copyright:
© Copyright 1968 American Mathematical Society
