Message Boards Message Boards

0
|
3038 Views
|
3 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Solve diophantine systems?

Posted 8 years ago

I have a Diophantine system Ax=b and Cx<=d where A and C are m*n matrices that I want to solve subject to the constraint that x consists of integers that are between 0 and k (inclusive). Looking through the documentation centre I have found the following tutorial regarding Diophantine polynomial systems (https://reference.wolfram.com/language/tutorial/DiophantineReduce.html) which uses the reduce function to solve the system. This works perfectly other than the fact that each equation and inequality must be entered separately, and I need to perform this for large systems. Ideally I would like to be able to call the function with the matrices directly, along the lines of

Reduce[A*x == b && C*x <= d && 0 <= x <= k, x, Integers]

to return all possible solutions for x. Is this possible with reduce, or any other function? Keeping in mind that I need all solutions to be returned. As a side note, I know that there are solutions to my system. Thanks.

POSTED BY: Mark Jonson
3 Replies

Check the Documentation Center page for LinearProgramming. It indicates how to specify Integers as the domain of interest.

POSTED BY: Daniel Lichtblau
In[5]:= Reduce[mat.vars == r, vars, Integers]

Out[5]= (C[1] | C[2]) \[Element] Integers && a == 2 + 8 C[1] && 
 b == 6 + 9 C[1] + 15 C[2] && c == -12 - 30 C[1] - 18 C[2] && 
 d == 9 + 20 C[1] + 11 C[2]
POSTED BY: Frank Kampas
In[3]:= mat = {{3, 4, 18, 24}, {27, 16, 28, 24}}; r = {30, 
  30}; vars = {a, b, c, d};

In[4]:= Reduce[Thread[mat.vars == r], vars, Integers]

Out[4]= (C[1] | C[2]) \[Element] Integers && a == 2 + 8 C[1] && 
 b == 6 + 9 C[1] + 15 C[2] && c == -12 - 30 C[1] - 18 C[2] && 
 d == 9 + 20 C[1] + 11 C[2]
POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract