Re: Resolve/Reduce is taking forever

*To*: mathgroup at smc.vnet.net*Subject*: [mg67259] Re: [mg67217] Resolve/Reduce is taking forever*From*: "Bonny Banerjee" <banerjee at cse.ohio-state.edu>*Date*: Wed, 14 Jun 2006 06:29:46 -0400 (EDT)*References*: <200606130507.BAA23755@smc.vnet.net> <917986B7-E756-4FC8-AA22-890245E9EDEC@mimuw.edu.pl>*Sender*: owner-wri-mathgroup at wolfram.com

That was very helpful. Thanks. Is there a text where I can find the complexity of Mathematica functions such as Reduce, Resolve, NMinimize, Select, etc. with respect to the number of variables? Please let me know. --Bonny. ----- Original Message ----- From: "Andrzej Kozlowski" <akoz at mimuw.edu.pl> To: mathgroup at smc.vnet.net Subject: [mg67259] Re: [mg67217] Resolve/Reduce is taking forever > *This message was transferred with a trial version of CommuniGate(tm) Pro* > On 13 Jun 2006, at 14:07, Bonny Banerjee wrote: > >> I am trying to write a simple function that determines the conditions >> for a >> curve to be on the left of a straight line. A curve is to the left of a >> straight line if each point on the curve is to the left of the straight >> line. The curve is specified using parametric equations: >> >> x -> a3Ã?t^3 + a2Ã?t^2 + a1Ã?t + a0 >> y -> b1Ã?t + b0 >> >> where t is the parameter, 0<=t<=1, and {a0, a1, a2, a3, b0, b1} are real >> coefficients. The straight line is specified using two points {x1,y1} >> and >> {x2,y2}. >> >> Here is the function: >> >> isLeftofLine[{x1_, y1_}, {x2_, y2_}, {a0_, a1_, a2_, a3_, b0_, b1_}] = >> Resolve[ >> ForAll[t, 0 <= t <= 1 => fxy[{x1, y1}, {x2, y2}, {a3Ã?t^3 + a2Ã?t^2 >> + >> a1Ã?t + a0, b1Ã?t + b0}] <= 0], >> {a0, a1, a2, a3, b0, b1}, Reals] >> >> where >> >> fxy[{x1_, y1_}, {x2_, y2_}, {x_, y_}] = >> (x - x1)Ã?(y2 - y1) - (y - y1)Ã?(x2 - x1) >> >> I tried Resolve and Reduce but both are taking forever. I waited for >> more >> than 4 hours but could not get any result from any of them. Considering >> this >> is a simple logical expression with only one universal quantifier, I am >> surprised at what might be taking so long. >> >> Any insights would be very helpful. Also, any alternative method for >> solving >> the same problem, such as using any other function in place of >> Reduce/Resolve or using a different representation for the curve or >> straight >> line, would be nice to know. I preferred using parametric equations for >> representing the curve as the curve is finite. >> >> Thanks, >> Bonny. >> > > > > First of all, your "function" will not work even, in this form, in a > thousand years, because you are demanding Mathematica to solve a purely > symbolic problem on the right hand side, before any numerical values have > been substituted for x1, x2,y1,y2. This is obviously impossible (see the > comments below) . So as a minimum you need to replace your immediate > assignment = by Delayed assignment :=, and substitute numerical values > for the x's and the y's. Your function should then look like this: > > isLeftofLine[{x1_, y1_}, {x2_, y2_},{a0_, a1_, a2_, a3_, b0_, b1_}] := > Resolve[ > ForAll[t, 0 <= t <= 1, fxy[{x1, y1}, {x2, y2}, {a3Ã?t^3 + a2Ã?t^2 + > a1Ã?t + a0, b1Ã?t + b0}] <= 0], > {a0, a1, a2, a3, b0, b1}, Reals] > > When you evaluate this with numerical values for the coordinates of the > points you will get a relationship between the a's and b's . However, > even if the problem is now correctly formulated it will take a very long > time to solve it. The algorithm that is needed, called > CylindricalAlgebraicDecomposition, is doubly exponential in the number of > variables (it is the number of variables and not the number of > quantifiers that counts). So let's try first solving a version of your > problem with a smaller number of unknowns, say 4. Here is the reduced > problem. > > fxy[{x1_, y1_}, {x2_, y2_}, {x_, y_}] = > (x - x1)Ã?(y2 - y1) - (y - y1)Ã?(x2 - x1) > > > isLeftofLine[{x1_, y1_}, {x2_, y2_}, {a_, b_, c_, d_}] := > Resolve[ > ForAll[t, 0 <= t <= 1 , fxy[{x1, y1}, {x2, y2}, {t^3 + > a*t^2 + b, c* t + d}] <= 0], > {a, b, c, d}, Reals] > > Now there are only four variables. Let's try some concrete values of > {x1,y1} and {x2,y2}. > > In[27]:= > cond=isLeftofLine[{0, 0}, {3, 4}, {a, b, c, d}] > > Out[27]= > b â?? Reals && ((a < -6 && ((c <= (1/3)*(8*a + 12) && > d >= (1/3)*(4*a + 4*b - 3*c + 4)) || > (Inequality[(1/3)*(8*a + 12), Less, c, LessEqual, > 0] && d >= (1/81)*(8*a^3 + 27*c*a + 108*b) + > (1/81)*Sqrt[64*a^6 + 432*c*a^4 + 972*c^2*a^2 + > 729*c^3]) || (c > 0 && d >= (4*b)/3))) || > (-6 <= a <= -3 && ((c <= (1/3)*(8*a + 12) && > d >= (1/3)*(4*a + 4*b - 3*c + 4)) || > ((1/3)*(8*a + 12) < c < 0 && > d >= (1/81)*(8*a^3 + 27*c*a + 108*b) + > (1/81)*Sqrt[64*a^6 + 432*c*a^4 + 972*c^2*a^2 + > 729*c^3]) || (c >= 0 && d >= (4*b)/3))) || > (-3 < a < -1 && ((c <= (1/3)*(-a^2 + 2*a + 3) && > d >= (1/3)*(4*a + 4*b - 3*c + 4)) || > ((1/3)*(-a^2 + 2*a + 3) < c < 0 && > d >= (1/81)*(8*a^3 + 27*c*a + 108*b) + > (1/81)*Sqrt[64*a^6 + 432*c*a^4 + 972*c^2*a^2 + > 729*c^3]) || (c >= 0 && d >= (4*b)/3))) || > (a >= -1 && ((c <= (1/3)*(4*a + 4) && > d >= (1/3)*(4*a + 4*b - 3*c + 4)) || > (c > (1/3)*(4*a + 4) && d >= (4*b)/3)))) > > > We can now use it to check the condition cond for various choices of > {a,b,c,d}, for example > > cond/.Thread[{a, b,c,d}->{2,3,4,5}] > > True > > So here is the good news and the bad news. I think that if I have > understood you correctly, your problem is solvable in theory. I strongly > doubt, however, that it is solvable in reasonable time. You can try out > the above on your computer and see how long it takes. Then remember: the > algorithm is double exponential in the number of variables so 4 hours > seems like a very optimistic estimate. > > Andrzej Kozlowski > Tokyo, Japan

**Follow-Ups**:**Re: Re: Resolve/Reduce is taking forever***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>

**References**:**Resolve/Reduce is taking forever***From:*"Bonny Banerjee" <banerjee@cse.ohio-state.edu>