Algorithms for the Solution of Systems of Linear Diophantine Equations

1982/11/01 by Tsu-Wu J. Chou, George E. Collins · 5 citations
Computer Science · Physics and Astronomy · Mathematics · #Polynomial and algebraic computation #Quantum chaos and dynamical systems #Commutative Algebra and Its Applications

paper · doi:10.1137/0211057

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.

Cited by

• Fast Computation of Smith Forms of Sparse Matrices Over Local Rings
• Efficient algorithm for linear diophantine equations in two variables
• Diophantine equations: a systematic approach
• On the Smith classes, the van Kampen obstruction and embeddability of [3]*K
• On the worst-case complexity of integer Gaussian elimination

Related

• Integer Algorithms to Solver Diophantine Linear Equations and Systems
• A Note on the Performance of Algorithms for Solving Linear Diophantine Equations in the Naturals
• A systematic approach to Diophantine equations: two thousand solved examples
• A systematic approach to Diophantine equations: open problems
• How to Solve Diophantine Equations