A fast method for finding the basis of non-negative solutions to a linear diophantine equation

• Type: Article in International Scientific Journal
• Date: 1995

Authors

Filgueiras, M (Author) FCUP; Tomas, AP (Author) FCUP

Journal

Title: Journal of Symbolic Computation

Vol. 19

Pages: 507-526

ISSN: 0747-7171

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 11 Citations

Scopus - 14 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-001-GV1

DOI: 10.1006/jsco.1995.1029

Abstract (EN): We present a complete characterization of the set of minimal solutions of a single linear Diophantine equation in three unknowns over the natural numbers. This characterization, for which we give a geometric interpretation, is based on well-known properties of congruences and we use it as the foundation of direct algorithms for solving this particular kind of equation. These direct algorithms and an enumeration procedure are then put together to build an algorithm for solving the general case of a Diophantine equation over the naturals. We also put forth a statistical method for comparing algorithms for solving Diophantine equations which is more sound than comparisons based on times observed for small sets of equations. From an extensive comparison with algorithms described by other authors it becomes clear that our algorithm is the fastest known to date for a class of equations. Typically the equations in this class have a small number of unknowns in one side, the maximum value for their coefficients being greater than 3.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 20