Mathematica 9 is now available
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: [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]
>>
>



  • Prev by Date: Re: Problems with ListPlot
  • Next by Date: Re: Re: Range of Use of Mathematica
  • Previous by thread: Re: "Reduce" wierdness (or too slow?)
  • Next by thread: Re: "Reduce" wierdness (or too slow?)