Algorithms for the Solution of Systems of Linear Diophantine Equations
Authors:
- Tsu-Wu J. ChouTCTsu-Wu J. Chou
- George E. CollinsGCGeorge E. Collins
- 1 November 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (4) , 687-708
Abstract
Two algorithms for the solution of linear Diophantine systems, which well restrain intermediate expression swell, are presented. One is an extension and improvement of Kannan and Bachem’s algorithm for the Smith and the Hermite normal forms of a nonsingular square integral matrix. The complexity of this algorithm is investigated and a polynomial time bound is derived. Also a much better coefficient bound is obtained compared to Kannan and Bachem’s analysis. The other is based on ideas of Rosser, which were originally used in finding a general solution with smaller coefficients to a linear Diophantine equation and in computing the exact inverse of a nonsingular square integral matrix. These algorithms are implemented by using the infinite precision integer arithmetic capabilities of the SAC-2 system. Their performances are compared. Finally future studies are mentioned.Keywords
This publication has 10 references indexed in Scilit:
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer MatrixSIAM Journal on Computing, 1979
- The algorithm description language ALDES (report)ACM SIGSAM Bulletin, 1976
- The Computing Time of the Euclidean AlgorithmSIAM Journal on Computing, 1974
- The Exact Solution of Systems of Linear Equations with Polynomial CoefficientsJournal of the ACM, 1973
- The Calculation of Multivariate Polynomial ResultantsJournal of the ACM, 1971
- Algorithms for Hermite and Smith normal matrices and linear Diophantine equationsMathematics of Computation, 1971
- Algorithm 288: solution of simultaneous linear Diophantine equations [F4]Communications of the ACM, 1966
- A method of computing exact inverses of matrices with integer coefficientsJournal of Research of the National Bureau of Standards, 1952
- A Note on the Linear Diophantine EquationThe American Mathematical Monthly, 1941
- A Note on the Linear Diophantine EquationThe American Mathematical Monthly, 1941