Solving Linear Diophantine Constraints Incrementally

Abstract: In this paper, we show how to handle linear Diophantine constraints incrementally by using several variations of the algorithm by Contejean and Devie (hereafter called ABCD) for solving linear Diophantine systems [2, 3]. The basic algorithm is based on a certain enumeration of the potential solutions of a system, and termination is ensured by an adequate restriction on the search. This algorithm generalizes a previous algorithm due to Fortenbacher [1], which was restricted to the case of a single equation. Note that using Fortenbacher’s algorithm for solving systems of Diophantine equations by repeatedly applying it to the successive equations is completely unrealistic: the tuple of variables in the solved equation must then be substituted in the rest of the system by a linear combination of the minimal solutions found in which the coefficients stand for new variables. Unfortunately, the number of these minimal solutions is actually exponential in both the number of variables and the value of the coefficients of the equation solved. In contrast, ABCD solves systems faster, without any intermediate blow-up, since it considers the system as a whole. Besides, and this is the new feature described in this paper, it can easily tolerate additional constraints such as membership constraints, linear monotonic inequations, and so on. This is due to the enumeration of tuples which allows a componentwise control of potential solutions. This is not the case with others (more recent) algorithms for solving systems of Diophantine equations, which are based on algebraic and combinatorial techniques [4, 5].

References

[1]

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

[2]

E. Contejean and H. Devie. Solving systems of linear diophantine equations. In Proc. 3rd Workshop on Unification, Lambrecht, Germany. University of Kaiserslautern, June 1989.

[3]

E. Contejean and H. Devie. Résolution de systèmes linéaires d’équations diophantiennes. Comptes-Rendus de l’Académie des Sciences de Paris, 313:115–120, 1991. Série I.

[4]

E. Domenjoud. Solving systems of linear diophantine equations: An algebraic approach. In Proc. 16th Mathematical Foundations of Computer Science, Warsaw, LNCS 520. Springer, 1991.

[5]

L. Pottier. Minimal solutions of linear diophantine systems : bounds and algorithms. In Proceedings of the Fourth International Conference on Rewriting Techniques and Applications, pages 162–173, Como, Italy, Apr. 1991.

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