Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found something odd about the time needed by Reduce to solve a polynomial inequality (under Wolfram Mathematica 8).

Consider the following:

Timing[Do[Reduce[-(519/197) - (257 x)/121 + (13 x^2)/20 - (16 x^3)/307 - x^4/
194 - x^5/4426 < 0, x, Reals], {1000}]]

On my computer it clocks at about 2.1 seconds. However the following:

Timing[Do[Reduce[-(947/350) - (557 x)/249 + (247 x^2)/350 < 0, x, 
Reals], {1000}]]

takes around 9.7 seconds.

In other words, the solving of an inequality of order 2 is five times slower then the solving of one of order 5!

To make the things even more interesting, I can "reproduce" this paradoxical effect (i.e. that a more complex equation is solved faster). If I modify my latter example by adding a third-order term (no matter how big or small), the solving immediately accelerates (!), for example this

Timing[Do[Reduce[-(947/350) - (557 x)/249 + (247 x^2)/350 + 10^(-30)*x^3 < 0, 
x, Reals], {1000}]]

as well as this

Timing[Do[Reduce[-(947/350) - (557 x)/249 + (247 x^2)/350 + 10^(30)*x^3 < 0, 
x, Reals], {1000}]]

takes about 1.6-1.7 seconds.

Either I am overlooking something trivial about how Mathematica solves these inequalities or something very strange is going on...

Thank you in advance!

share|improve this question

closed as off topic by Listing, Zhen Lin, Jonas Meyer, Asaf Karagila, Mariano Suárez-Alvarez Dec 31 '11 at 5:18

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
I voted to close as I don't think this can be properly answered. Mathematica uses closed source and very complicated algorithms and doesn't use special strucutres when handling polynomials, therefore the runtimes doesn't mainly depend on the degree of the polynomial. –  Listing Dec 29 '11 at 22:00
    
Yes, it's clear that only a Mathematica engineer could "profile" the code (for example), neverthless, I hope that there is a logical explanation for the phenomenon that making an inequality more complex (or just almost "infinitesimally" more complex) cuts the running time to solve it by a magnitude... without the need to know the source code. –  Tamas Ferenci Dec 29 '11 at 22:14
    
Especially because "code optimization" is something that every user should be able to perform... and this problem can be very well formulated as an optimization question. I know that it has a wide literature for Mathematica, however, I am not specifically familiar with it, that's why I have written, that I might be perhaps overlooking something well-known. –  Tamas Ferenci Dec 29 '11 at 22:20
    
Speculation (warning I'm not familiar with Mathematica): They use different algorithms, one inequality might be solved with Tarski's quantifier elimination, and the other by solving corresponding polynomial equation, and the condition/treshold of choosing one algorithm over another was chosen wrong. –  sdcvvc Dec 30 '11 at 1:17
    
You should ask this in Mathematica's user mailing list. Here this is rather off-topic. –  Mariano Suárez-Alvarez Dec 31 '11 at 5:18
add comment

Browse other questions tagged or ask your own question.