 mersenneforum.org large equation system over integers
 Register FAQ Search Today's Posts Mark Forums Read  2011-03-28, 21:20   #12
flouran

Dec 2008

15018 Posts Quote:
 Originally Posted by talork Does anyone know an efficient way to solve this?
A paper by Giusti-Heintz-Hägele-Morais-Pardo-Montaña provides a rather effective algorithm for the solving of multivariate polynomial systems by way of Hilbert's Nullstellensantz:

http://arxiv.org/pdf/alg-geom/9608010v1

However, I am not so sure an actual implementation of the algorithm (based on the Newton-Hensel lifting method) would be easy to do.

Last fiddled with by flouran on 2011-03-28 at 21:40   2011-03-29, 00:09   #13
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 Originally Posted by flouran A paper by Giusti-Heintz-Hägele-Morais-Pardo-Montaña provides a rather effective algorithm for the solving of multivariate polynomial systems by way of Hilbert's Nullstellensantz: http://arxiv.org/pdf/alg-geom/9608010v1
For this problem, that approach will be extremely slow.   2011-03-29, 00:12   #14
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by science_man_88 couldn't it also be reduce to actually using Code: (17:57)>3+1 %67 = 4 (17:57)>2+1+1 %68 = 4 (17:57)>1+1+1+1 %69 = 4 (17:57)>2+2 %70 = 4 (17:57)>4+0 %71 = 4 for the pure 4 one there are 15 possible combo's I see with 15 variables. the second has around 15*14 I believe. and yes I know I used the same logic ( or no logic, depends who reads it) in the chess positions thread.
I get 3060 possibilities for a given equation. 3060^651 is too large, so direct enumeration is out.   2011-03-29, 01:48   #15
wblipp

"William"
May 2003
New Haven

26·37 Posts Quote:
 Originally Posted by talork the variables should all be non negative and the right side of the equation is always 4. here are a few equations for example: x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15=4 x12+x166+x180+x192+x204+x216+x228+x232+x241+x250+x259+x268+x277+x286+x295=4 x85+x225+x352+x479+x579+x679+x779+x1335+x1343+x1351+x1359+x1367+x1375+x1383+x1391=4
Are there always exactly 15 variables, too? I'm wondering if there is some underlying structure to this problem that can simplify things. For example, maybe it is a Latin Squares question in disguise. Can you tell us more about the source of the problem?   2011-03-29, 07:23 #16 talork   Mar 2011 2·3 Posts Thanks for all the ideas. So far, I've tried using backtracking (with all the trimming I could find), but the results aren't satisfying at all (more than 24 hours and still no answer). There are exactly 15 variables in each equation, and the equations are symmetric, meaning each variable appears in exactly 7 equations. The variables are mixed in such way that there aren't any independent sets of variables and there are no repetitions of equations or dead variables. Does anyone know if the function bintprog (Matlab) should be able to assist in this case? Thanks again for your help   2011-03-29, 11:24   #17
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by talork Thanks for all the ideas. So far, I've tried using backtracking (with all the trimming I could find), but the results aren't satisfying at all (more than 24 hours and still no answer). There are exactly 15 variables in each equation, and the equations are symmetric, meaning each variable appears in exactly 7 equations. The variables are mixed in such way that there aren't any independent sets of variables and there are no repetitions of equations or dead variables. Does anyone know if the function bintprog (Matlab) should be able to assist in this case? Thanks again for your help

couldn't you set two equations equal and eventually get an equation that replaces one variable with 2 then you can say variable=variable+variable or what ever the case may be.   2011-03-29, 12:52 #18 talork   Mar 2011 2×3 Posts I don't see how this is possible, since (and sorry if i didn't mention it) any 2 equations have at most 1 common variable   2011-03-29, 13:18   #19
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts Quote:
 Originally Posted by talork I don't see how this is possible, since (and sorry if i didn't mention it) any 2 equations have at most 1 common variable
this complicates things but I think I still see a way:

x+y+z = 4
a+x+b = 4
a+b=y+z

also if

x+y+z = 4
c-x+d = 4
(c+d)-(y+z) = 2*x

so you can use the common variable somehow to set up more relations.   2011-03-29, 14:21   #20
Wacky

Jun 2003
The Texas Hill Country

100010000012 Posts Quote:
 Originally Posted by wblipp For example, maybe it is a Latin Squares question in disguise. Can you tell us more about the source of the problem?
I will repeat William's request. Show us the framework from which the equations are derived.

I suspect that your variables and equations could be expressed in a matrix notation that would be much simpler. In addition, if the equations express only the structure of the constraints, it is highly likely that there are many symmetrical solutions. Many of the solution techniques will fail under these circumstances, but they can succeed if you eliminate the symmetrically equivalent solutions by adding a few more constraints.   2011-03-29, 14:38 #21 talork   Mar 2011 2·3 Posts Unfortunately I only have the equations... Would it help if I uploaded them and/or their matrix representation?   2011-03-29, 16:10   #22
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by talork Unfortunately I only have the equations... Would it help if I uploaded them and/or their matrix representation?
well I would like the equations myself.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 4 2017-02-03 12:48 flouran Math 7 2009-12-12 18:48 Vijay Math 6 2005-04-14 05:19 jasong Math 2 2005-03-11 03:30 Logic Programming 1 2004-09-19 21:26

All times are UTC. The time now is 14:07.

Sun Oct 24 14:07:41 UTC 2021 up 93 days, 8:36, 0 users, load averages: 1.39, 1.19, 1.16