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>