mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2011-03-28, 21:20   #12
flouran
 
flouran's Avatar
 
Dec 2008

15018 Posts
Post

Quote:
Originally Posted by talork View Post
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
flouran is offline   Reply With Quote
Old 2011-03-29, 00:09   #13
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by flouran View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-29, 00:12   #14
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-29, 01:48   #15
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

26·37 Posts
Default

Quote:
Originally Posted by talork View Post
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?
wblipp is offline   Reply With Quote
Old 2011-03-29, 07:23   #16
talork
 
Mar 2011

2·3 Posts
Default

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
talork is offline   Reply With Quote
Old 2011-03-29, 11:24   #17
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by talork View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-29, 12:52   #18
talork
 
Mar 2011

2×3 Posts
Default

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
talork is offline   Reply With Quote
Old 2011-03-29, 13:18   #19
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by talork View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-29, 14:21   #20
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

100010000012 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
Wacky is offline   Reply With Quote
Old 2011-03-29, 14:38   #21
talork
 
Mar 2011

2·3 Posts
Default

Unfortunately I only have the equations...
Would it help if I uploaded them and/or their matrix representation?
talork is offline   Reply With Quote
Old 2011-03-29, 16:10   #22
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by talork View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Large Polynomial Equation Problem carpetpool carpetpool 4 2017-02-03 12:48
Diophantine Equation flouran Math 7 2009-12-12 18:48
Possible solutions to an equation: Vijay Math 6 2005-04-14 05:19
Time to prp equation jasong Math 2 2005-03-11 03:30
Request for an equation. 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.