2
$\begingroup$

I have a large, under-determined system (60 equations and 116 unknowns) of linear Diophantine equations. I am aware of the algorithms typically used to solve these systems, which is not my question.

I have solved the system in Mupad and Mathematica for a parametric solution set. I have confirmed that the system has a bounded, finite set of integer solutions, and I am only interested in non-negative solutions.

I am looking for a way to:

  1. derive (or estimate) the size of the reduced (i.e., non-negative) solution set, it seems that this can possibly be done using generating functions, although I can't find a good reference for performing this calculation in this instance; and

  2. fully enumerate all non-negative solutions.

Given the size of the system, Mathematica seems to give up no matter how much memory I allocate to enumerating all of the solutions using Reduce[].

I am aware of a paper by Papp & Vizvari (2006) J. Mathematical Chemistry that solved such a system using several different algorithms and then enumerated all solutions following the method laid out in Land and Doig, but their paper does not give a lot of detail in the approach.

I would appreciate any direction to texts or resources that describe the estimation of the solution set and an efficient enumeration approach if they exist.

Thank you for your help.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The problem you are describing is equivalent to finding all of the integer points inside a high-dimensional polytope. Barvinok's algorithm is able to enumerate all solutions (with the output taking the form of a generating function). For more details about this theory, and for an implementation (called LattE), take a look at the website here.

A warning: I've successfully used LattE to deal with 9 or 10-dimensional polytopes. It sounds like you're working with one which is 56-dimensional and, depending on how simple it is, this may be way more than the algorithm can handle.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this. I haven't had a lot of luck compiling any of the few versions of Latte that I've tried, but will keep at it. I suspect that the dimensionality problem you mention will be a problem. $\endgroup$
    – Andrew
    May 22, 2014 at 14:02
  • $\begingroup$ The LattE website has some pre-compiled binaries. Also, you can e-mail your polytope to the LattE people and they can (try) to run it for you. $\endgroup$
    – Jeremy Rouse
    May 22, 2014 at 15:41
0
$\begingroup$

For enumeration you can try ISL.

Need to convert the problem to its format and run isl_polytope_scan

Sample session:

 $ ./isl_polytope_scan 
 {[x,y] : 0 <= x <= 10 and 0 <= y <= 10 and x+y=6}
 [[1,6,0]
  [1,5,1]
  [1,4,2]
  [1,3,3]
  [1,2,4]
  [1,1,5]
  [1,0,6]]

Ignore the leading $1$ in the output.

Improve this answer
$\endgroup$
5
  • $\begingroup$ How well does this scale up to 60 equations in 116 unknowns? $\endgroup$
    – Gerry Myerson
    May 19, 2014 at 5:28
  • $\begingroup$ @GerryMyerson Haven't checked exactly enumeration, but solving works for hundreds variables. If the number of solutions is quite large it will be clearly slow just to print solutions. $\endgroup$
    – joro
    May 19, 2014 at 5:58
  • $\begingroup$ I was unable to return a solution for my problem using ISL. I confirmed that it was able to solve a reduced form of the problem with only 5 unknowns in 4 equations, but it returned 'null matrix' on the full problem after running for about 12 hours. I confirmed that this was not because there is no solution to the system by running FindInstance[] in Mathematica on the full problem, which was able to find a solution very quickly. See link for my bash script. $\endgroup$
    – Andrew
    May 22, 2014 at 14:00
  • $\begingroup$ @Andrew don't know, it might be a bug in ISL, consider reporting it. (Less likely it might be a problem in your encoding). $\endgroup$
    – joro
    May 22, 2014 at 15:17
  • $\begingroup$ @Andrew If you have more than say 2^50 solutions, you can't enumerate them with current hardware since just printing will be slow (and in addition you will run out of disk space if you try to save them). btw, ISL's isl_polyhedron_sample returns one solution to input in the same format, does it work for the full problem? $\endgroup$
    – joro
    May 22, 2014 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.