Re: "Reduce" wierdness (or too slow?)
- To: mathgroup at smc.vnet.net
- Subject: [mg89020] Re: [mg88996] "Reduce" wierdness (or too slow?)
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 24 May 2008 03:51:11 -0400 (EDT)
- References: <200805230707.DAA25801@smc.vnet.net>
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?)