Re: Re: Resolve/Reduce is taking forever
- To: mathgroup at smc.vnet.net
- Subject: [mg67289] Re: [mg67259] Re: [mg67217] Resolve/Reduce is taking forever
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Thu, 15 Jun 2006 03:27:17 -0400 (EDT)
- References: <200606130507.BAA23755@smc.vnet.net> <917986B7-E756-4FC8-AA22-890245E9EDEC@mimuw.edu.pl> <200606141029.GAA28252@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
I don't think there can be any simple answer to this kind of
question. For example, Reduce, uses a variety of algorithms depending
on the type of problem it is applied to: among them Groebner Basis,
Cylindircal Algebraic Decomposition and others (see the
Implementation Notes for Reduce, Resolve, Minimize etc.) They all
have different complexity, which can be checked in standard texts on
symbolic algebra, such as Mishra, Algorithmic Algebra, Springer 1993.
In fact, Mathematica does not always use the very latest and most
efficient algorithms (which is not really surprising in a general
purpose CAS).
The really important thing is to remember that Reduce (as well as
Resolve, Minimize, Maximize etc) use only exact methods which means
that they are SLOOOW. (Sometimes, I feel, such algorithms have more
aesthetic than practical value but I love them ;-) To be quite
correct, however, these functions also quite often use so called
"validated numerical methods", which also produce "exact" results but
are somewhat faster). The situation is completely different with
numerical algorithms used by NMinimize, NSolve, FindRoot etc: they
are generally fast but can at best provide bounds for exact answers.
Select, of course, is of a completely different kind of creature; it
obviously makes use of some kind of search algorithm and symbolic
algebra is used only to the extent that it is used by the function
specified as the second argument to Select. So the question about the
"complexity with respect to the number of variables" reduces to the
same question for the selection functions used.
Andrzej Kozlowski
On 14 Jun 2006, at 19:29, Bonny Banerjee wrote:
> 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: [mg67289] [mg67259] Re: [mg67217] Resolve/Reduce is taking forever
>
>
>> 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: Re: Resolve/Reduce is taking forever
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: Re: Re: Resolve/Reduce is taking forever
- References:
- Resolve/Reduce is taking forever
- From: "Bonny Banerjee" <banerjee@cse.ohio-state.edu>
- Re: Resolve/Reduce is taking forever
- From: "Bonny Banerjee" <banerjee@cse.ohio-state.edu>
- Resolve/Reduce is taking forever