An Efficient Incremental Algorithm for Solving Systems of Linear Diophantine Equations

Abstract: In this paper, we describe an algorithm for solving systems of linear Diophantine equations based on a generalization of an algorithm for solving one equation due to Fortenbacher [1]. It can solve a system as a whole, or be used incrementally when the system is a sequential accumulation of several subsystems. The proof of termination of the algorithm is difficult, whereas the proofs of completeness and correctness are straightforward generalizations of Fortenbacher’s proof.

References

[1]

M. Clausen and A. Fortenbacher. Efficient solution of linear diophantine equations. Journal of Symbolic Computation, 8(1&2):201–216, 1989.

This document was translated from L^AT_EX by H^EV^EA.