Algorithms for the Solution of Systems of Linear Diophantine Equations
Copyright policy )Algorithms for the Solution of Systems of Linear Diophantine Equations
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.
Canonical forms, reductions, classification, Other matrix algorithms, infinite precision integer arithmetic, linear Diophantine system, Direct numerical methods for linear systems and matrix inversion, Matrices of integers, Rosser-type algorithm, solution module basis, Kannan-Bachem algorithm, Linear Diophantine equations, Hermite normal form
Canonical forms, reductions, classification, Other matrix algorithms, infinite precision integer arithmetic, linear Diophantine system, Direct numerical methods for linear systems and matrix inversion, Matrices of integers, Rosser-type algorithm, solution module basis, Kannan-Bachem algorithm, Linear Diophantine equations, Hermite normal form
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).64 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!