Re: Counting real roots of integer polynomials

[Dirk Laurie <dirk.laurie@gmail.com>]

You don't need polrootsreal. A Sturm sequence is adequate. Since your
polynomials have integer coefficients, you can do it in rational
arithmetic if necessary.

https://en.wikipedia.org/wiki/Sturm%27s_theorem

2018-06-07 8:37 GMT+02:00 Gordon Royle <gordon.royle@uwa.edu.au>:
> Hi,
>
> I have a large number (hundreds of millions) of integer polynomials of moderate degree (about 15-20) and coefficients (less than 6 digits each). They may have complex roots, but I just want to collect data about certain real roots.
>
> In particular, I want to know
>
> (1) How many roots the polynomial has in the open interval (1,2)
> (2) The multiplicity (possibly 0) of 2 as a root
>
> For other reasons, I am sure that x=1 is a simple root of each of these polynomials.
>
>
> At the moment I do the following:
>
> - count the roots in the closed interval [1,2] with “polrootsreal” with argument [1,2]
> - count the roots at 2 by using polrootsreal again with argument [2,2]
> - subtract the second value from the first value and take off another 1
>
> I am not sure if I should do something else instead - maybe factor the polynomial to find the multiplicity of the root at 2, and save one call to polrootsreal?
>
> Being primarily an end-user of polynomial routines, I do not have a feel for the relative costs for factoring versus solving etc; though I could probably try some simple experiments there may be a more sophisticated way of addressing my problem that I would just never come across.
>
> Any advice will be gratefully received.
>
> Thanks
>
> Gordon