Re: "Reduce" wierdness (or too slow?)
- To: mathgroup at smc.vnet.net
- Subject: [mg89033] Re: [mg88996] "Reduce" wierdness (or too slow?)
- From: Adam Strzebonski <adams at wolfram.com>
- Date: Sat, 24 May 2008 03:53:39 -0400 (EDT)
- References: <200805230707.DAA25801@smc.vnet.net> <2F0C376C-1C98-4F71-9DB5-2DA8CEC86836@mimuw.edu.pl> <DC6E4149-32C8-44E6-9A50-5FCB0B0459C8@mimuw.edu.pl>
- Reply-to: adams at wolfram.com
Reduce separates equations from inequalities and solves the equations
using GroebnerBasis only if the equations have a finite number of
solutions. Solving a positive-dimensional system of nonlinear equations
using GroebnerBasis is likely to produce a solution parametrization
involving algebraic functions given as Root objects. Using such
parametrization as input to Cylindrical Algebraic Decomposition makes
the problem harder not easier. In this particular example GroebnerBasis
gives a simple parametrization which involves only one square radical
and no Root functions. However, to know that, one has to compute
the Groebner basis. I don't think Reduce should do it automatically,
since in "most" cases the result would not be useful and Groebner
basis computation can be slow too...
Best Regards,
Adam Strzebonski
Wolfram Research
Andrzej Kozlowski wrote:
> On reconsidering the problem, I am begining to wonder if Reduce is not
> doing something wrong here. I seems to me that separating equations from
> inequalities is exactly what it would normally do, so I am not any more
> sure what accounts for the differnce in performance between the very
> fast code below and this extremly slow one:
>
> p = And @@ {t7 > 0, t7 > t1, t7 > t2, t7 > t3,
> t7 > t4, t7 > t5, t7 > t6}
>
> Timing[rr =
> Reduce[
> And @@ {1000 + t2 == t3, 1200 + w1 == w2, 125 + t1 == t2, 125 + t5
> == t6,
> k*t3 == (v2 + z2)/2,
> t7*z1 + t2*z2 + z3 + z4 == H + k*t2^2 + k*t7^2 + w1,
> t7*z1 + t3*z2 + z3 + z4 == H + k*(t3^2 + t7^2),
> t7*z1 + z3 + z4 == 2*H + k*t7^2, w1 + t6*z1 + z3 == k*t6^2 + w1 +
> w2,
> w1 == w2 + (t1 - t2)*(k*t1 + k*t2 - z2),
> w2 + t5*z1 + z3 == k*t5^2 + w1 + w2, w2 == (-k)*t1^2 + t1*z2 + z4,
> z1 == 2*k*t4 + v2, z2 == 0, k*t1^2 + w2 == H + t1*z2} && p, {H,
> t1, t2,
> t3, t4, t5, t6, t7, v2, w1, w2, z1, z2, z3, z4}];]
>
> One should not forget that solving inequalities by algorithmic methods
> can be quite frustrating. For example:
>
> Reduce[{x^20 + y^20 + x^10 y^3 + 1 == 0, x^4 + y^21 + x y + 2 == 0, x > 0,
> y > 0}, {x, y}] // Timing
> {30.2435, False}
>
> took over half a minute but a human being of average intelligence should
> be able to do it in under 1 second.
>
> Andrzej Kozlowski
>
>
>
>
> On 23 May 2008, at 21:19, Andrzej Kozlowski wrote:
>
>> To solve inequalities Reduces uses an algorithm from real algebraic
>> geometry (due to G. E. Collins) known as Cylindrical Algebraic
>> Decomposition (In Mathematica implemented as simply
>> CylindricalDecomposition). This algorithm is known to have double
>> exponential complexity in the number of variables. If you add
>> inequalities to the original equations, Reduce calls on
>> CylindricalDecomposition on the entire input and in view of the above
>> complexity, if you are seeing only exponential time growth, I would
>> say Reduce is doing rather well!
>>
>> On the other hand, in this particualr case, we can try to apply a bit
>> of human intelligence and separate equation solving (relatively fast)
>> from ineqality solving (slow).
>>
>> In[1]:= Timing[rr = Reduce[And @@ {1000 + t2 == t3,
>> 1200 + w1 == w2, 125 + t1 == t2,
>> 125 + t5 == t6, k*t3 == (v2 + z2)/2,
>> t7*z1 + t2*z2 + z3 + z4 == H + k*t2^2 +
>> k*t7^2 + w1, t7*z1 + t3*z2 + z3 + z4 ==
>> H + k*(t3^2 + t7^2), t7*z1 + z3 + z4 ==
>> 2*H + k*t7^2, w1 + t6*z1 + z3 ==
>> k*t6^2 + w1 + w2, w1 ==
>> w2 + (t1 - t2)*(k*t1 + k*t2 - z2),
>> w2 + t5*z1 + z3 == k*t5^2 + w1 + w2,
>> w2 == (-k)*t1^2 + t1*z2 + z4,
>> z1 == 2*k*t4 + v2, z2 == 0, k*t1^2 + w2 ==
>> H + t1*z2}, {H, t1, t2, t3, t4, t5, t6, t7,
>> v2, w1, w2, z1, z2, z3, z4}]; ]
>> Out[1]= {0.06673299999999999, Null}
>> In[2]:= p = And @@ {t7 > 0, t7 > t1, t7 > t2, t7 > t3,
>> t7 > t4, t7 > t5, t7 > t6};
>> In[3]:= Timing[Reduce[rr && p, {H, t1, t2, t3, t4, t5, t6,
>> t7, v2, w1, w2, z1, z2, z3, z4}]; ]
>> Out[3]= {0.6671069999999999, Null}
>>
>> Of course this may not be the answer you want as the answer depends on
>> the order in which you list the variables and different orders will
>> produce not only different answers but also very different performance.
>>
>> Andrzej Kozlowski
>>
>>
>> On 23 May 2008, at 16:07, TuesdayShopping wrote:
>>
>>> Following equations solve (H, z4 and a couple of others are fully
>>> solved; others are not solved; that is OK) in a fraction of a second.
>>> If I add the inequalities ONE AT A TIME "t7 > 0, t7 > t1, t7 > t2, t7
>>> > t3, t7 > t4, t7 > t5, t7 > t6", the time taken for "Reduce" will
>>> will go up exponentially; after the inequation "t7>t3" it will not
>>> even complete in 600 seconds!
>>>
>>> Is "Reduce" buggy? Any idea how I can still use Reduce to solve the
>>> set with inequations (a solution like "OK. . so do not use the
>>> inequations with Reduce" is not a solution because I isolated the
>>> inequations after a lot of time trying various things and may not be
>>> able to do that for all the problems; and sometimes I do need the
>>> inequations in order to limit the result set)
>>>
>>> Thanks a lot for any input into this.
>>>
>>> InputForm[AbsoluteTiming[TimeConstrained[Reduce[
>>> {1000 + t2 == t3
>>> , 1200 + w1 == w2
>>> , 125 + t1 == t2
>>> , 125 + t5 == t6
>>> , k*t3 == (v2 + z2)/2
>>> , t7*z1 + t2*z2 + z3 + z4 == H + (k*t2^2) + (k*t7^2) + w1
>>> , t7*z1 + t3*z2 + z3 + z4 == H + (k*(t3^2 + t7^2))
>>> , t7*z1 + z3 + z4 == 2*H + (k*t7^2)
>>> , w1 + t6*z1 + z3 == (k*t6^2) + w1 + w2
>>> , w1 == w2 + ((t1 - t2)*(k*t1 + k*t2 - z2))
>>> , w2 + t5*z1 + z3 == (k*t5^2) + w1 + w2
>>> , w2 == (-k*t1^2) + t1*z2 + z4
>>> , z1 == (2*k*t4) + v2
>>> , z2 == 0
>>>
>>>
>>> ,(k*t1^2)+w2==H+t1*z2
>>>
>>>
>>> }, {g, H, t1, t2, t3, t4, t5, t6, t7, v2, w1, w2, z1, z2, z3,
>>> z4}], 120, TimedOut]], NumberMarks -> False]
>>>
>>
>
- References:
- "Reduce" wierdness (or too slow?)
- From: TuesdayShopping <TuesdayShopping@yahoo.com>
- "Reduce" wierdness (or too slow?)