MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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 


  • Prev by Date: Re: Resolve/Reduce is taking forever
  • Next by Date: Re: Determining continuity of regions/curves from inequalities
  • Previous by thread: Re: Resolve/Reduce is taking forever
  • Next by thread: Re: Re: Resolve/Reduce is taking forever