Sylvester’s identity and multistep integer-preserving Gaussian elimination
HTML articles powered by AMS MathViewer
- by Erwin H. Bareiss PDF
- Math. Comp. 22 (1968), 565-578 Request permission
Abstract:
A method is developed which permits integer-preserving 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 (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 $A$ is nearly singular.References
-
E. H. Bareiss, Multistep Integer-Preserving Gaussian Elimination, Argonne National Laboratory Report ANL-7213, May, 1966.
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.
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, Integer-Preserving Gaussian Elimination, Program P-158 (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), 565-578
- MSC: Primary 65.35
- DOI: https://doi.org/10.1090/S0025-5718-1968-0226829-0
- MathSciNet review: 0226829