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>
- Re: Re: Resolve/Reduce is taking forever
- References:
- Resolve/Reduce is taking forever
- From: "Bonny Banerjee" <banerjee@cse.ohio-state.edu>
- Resolve/Reduce is taking forever