# Paradox running times of Reduce for polynomial inequalities in Mathematica 8 [closed]

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!

-
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