Re: Number of real roots of a polynomial

[Pascal Molin <molinp@math.jussieu.fr>]

polsturm is exactly what you want.

--

Pascal

2013/5/24 Charles Greathouse <charles.greathouse@case.edu>

Given a univariate polynomial, how can I determine the number of real solutions with gp?

Usually I look at polroots(P) and count the number of roots which have an imaginary part which 'looks like' 0. But I'd like a solution that certifies that the zeros are not merely close to being real.

A solution giving the number of distinct real roots would be equally useful for me. Speed is important in this application, so if there's a good way to do it with the library that would be fine (though I'm just using GP now).

In my case these are cubics in Z[x] so there are analytic criteria available but they seem a bit complicated -- putting the full problem into Mathematica and simplifying gave an _expression_ with LeafCount over 8000 -- that is, the number of operators and function calls was nearly 10^4. No doubt careful storing of partial results can reduce the algorithmic complexity but I don't expect it to be quick in any case (trusting here, somewhat unsteadily, to the reliability of Mathematica).

Charles Greathouse
Analyst/Programmer
Case Western Reserve University