Re: "Reduce" wierdness (or too slow?)
- To: mathgroup at smc.vnet.net
- Subject: [mg89022] Re: [mg88996] "Reduce" wierdness (or too slow?)
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 24 May 2008 03:51:33 -0400 (EDT)
- References: <200805230707.DAA25801@smc.vnet.net> <2F0C376C-1C98-4F71-9DB5-2DA8CEC86836@mimuw.edu.pl>
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?)