8
$\begingroup$

So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem is, they give the algorithm on pages 350-351, but part of step (3) appears to be missing.

My question for MathOverflow is, therefore, whether anyone knows either of another such algorithm or has an idea as to what the missing part of Gao and Dong's algorithm is.

Improve this question
$\endgroup$
4
  • $\begingroup$ @Joseph O'Rourke: The question you linked to is on systems of linear + quadratic Diophantine equations, whereas this one restricts to linear Diophantine equations. $\endgroup$
    – j.c.
    Commented Jul 11, 2011 at 1:56
  • 1
    $\begingroup$ Please review: "Algorithms for solving systems of linear Diophantine inequalities," a previous MO question: mathoverflow.net/questions/37637… , whose title differs by just one character (pluralizing 'Algorithm'). $\endgroup$
    – Joseph O'Rourke
    Commented Jul 11, 2011 at 1:58
  • $\begingroup$ @jc: Point taken! $\endgroup$
    – Joseph O'Rourke
    Commented Jul 11, 2011 at 1:59
  • $\begingroup$ What's the complexity of their algorithm? $\endgroup$
    – Michael Wehar
    Commented Feb 15, 2015 at 23:31

2 Answers 2

Reset to default
6
+50
$\begingroup$

Mathematica implements an algorithm: see the manual here:

MathematicaDiophantine
(Added in response to a comment query.)

The paper

Hochbaum, Dorit S., and Anu Pathria. "Can a System of Linear Diophantine Equations be Solved in Strongly Polynomial Time?." (1994). (PDF download link)

says that "no strongly polynomial algorithm exists for the problem of finding the set of solutions to a system of linear diophantine equations in the complexity model allowing the operations $\{ +, -, \times, /, \bmod, < \}$." But if one assumes the gcd can be found quickly, then the system can be solved in strongly polynomial time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you happen to know about the complexity of determining whether or not a system of inequalities has integer solutions? $\endgroup$
    – Michael Wehar
    Commented Feb 16, 2015 at 0:57
  • $\begingroup$ Awesome! Thank you very much. I appreciate it. :) $\endgroup$
    – Michael Wehar
    Commented Feb 16, 2015 at 4:31
6
$\begingroup$

GAP provides a function NullspaceIntMat which solves systems of linear diophantine equations. The documentation says:

25.1-2 SolutionIntMat

* SolutionIntMat( mat, vec ) ───────────────────────────────────── operation

If  mat  is  a  matrix  with integral entries and vec a vector with integral
entries,  this  function  returns  a vector x with integer entries that is a
solution  of  the  equation x * mat = vec. It returns fail if no such vector
exists.

────────────────────────────────  Example  ─────────────────────────────────
  gap> mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];;
  gap> SolutionMat(mat,[95,115,182]);
  [ 47/4, -17/2, 67/4, 0, 0 ]
  gap> SolutionIntMat(mat,[95,115,182]);
  [ 2285, -5854, 4888, -1299, 0 ]
────────────────────────────────────────────────────────────────────────────

The source code can be found in the file lib/matint.gi included in the GAP distribution.

There is also a function SolutionNullspaceIntMat which additionally computes a basis of the integral nullspace of the given matrix.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .