Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

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]
>



  • Prev by Date: Re: Re: Interpolation and plot doing strange things with
  • Next by Date: Re: Problems with ListPlot
  • Previous by thread: "Reduce" wierdness (or too slow?)
  • Next by thread: Re: "Reduce" wierdness (or too slow?)