2
$\begingroup$

Is there a way to efficiently find the number of real roots of a polynomial $P$ in a range $[a,b]$ with $a,b \in \mathbb{R}$? You may/may not know much about the coefficients of the polynomial, so I want methods that work based on the fact that it's a polynomial.

EDIT: I know about Sturm's theorem, but I think it would be too slow for my use case (polynomial of around degree 30), as I have to generate at most n polynomials, n being the degree of the original polynomial.

$\endgroup$
3
  • 1
    $\begingroup$ " I knew about Sturm's theorem, but I thought it was too slow (have to generate at most n polynomials, n being the degree of the original polynomial), but I didn't think to do the Descartes' thing-- however, I have a polynomial of around 30, so I don't know if it would be efficient." Please include this type of information in the question post via an edit $\endgroup$
    – quid ♦
    Aug 1, 2020 at 1:10
  • $\begingroup$ @quid Thank you for your advice. Done. $\endgroup$
    – DUO Labs
    Aug 2, 2020 at 19:41
  • 1
    $\begingroup$ I reopened on the edit $\endgroup$
    – quid ♦
    Aug 2, 2020 at 19:44

2 Answers 2

Reset to default
2
$\begingroup$

Use Sturm's theorem.

For low degrees, one can frequently translate the variable $x \mapsto x -a$ and $x \mapsto x-b$, apply Descartes' rule of signs to each, and also get the desired result.

$\endgroup$
11
  • $\begingroup$ @EricTowers I knew about Sturm's theorem, but I thought it was too slow (have to generate at most $n$ polynomials, $n$ being the degree of the original polynomial), but I didn't think to do the Descartes' thing-- however, I have a polynomial of around $30$, so I don't know if it would be efficient. $\endgroup$
    – DUO Labs
    Aug 1, 2020 at 0:19
  • $\begingroup$ @DUO : Exponential search to get the bounds of an interval containing all the roots, then binary search to partition that into subintervals each containing a simple real root or bounding a pair of complex conjugate roots. (This assumes all your zeroes are simple -- not repeated. First divide out by the polynomial GCD of your polynomial and its derivative. (continued) $\endgroup$
    – Eric Towers
    Aug 2, 2020 at 18:35
  • $\begingroup$ @DUO : (continues) A repeated root of degree $n$ has degree $n-1$ in the derivative.) Alternatively, use Sturm sequences. Computing derivatives of polynomials is mechanical. And then you evaluate the collection of about 30 polynomoals to determine if you have a partition element containing two eral roots (so should be subdivided) or a complex conjugate pair, so should not. Of course, at that, skip the messing around with translation and Descartes' rule. $\endgroup$
    – Eric Towers
    Aug 2, 2020 at 18:38
  • $\begingroup$ How can you use exponential search on a polynomial (it only works on sorted lists), or am I missing something? $\endgroup$
    – DUO Labs
    Aug 2, 2020 at 19:50
  • 1
    $\begingroup$ Descartes' rule only gives a bound on the number of roots. $\endgroup$
    – user65203
    Aug 2, 2020 at 19:59
0
$\begingroup$

I am afraid there is no free lunch. The analytical expression of the number of real roots of a polynomial is precisely the one generated by the Sturm sequence, and no simplification has been found so far (AFAIK). So the direct method is Sturm's.

Other approaches (such as based on Descartes's rule) will require iterations, the number of which is unpredictable and worsens as the roots get closer to each other. (An efficient implementation can be obtained by converting the polynomial to the Bernstein basis and exploiting the "hull property" - if some coefficient differ in sign, there must be a zero. Then a dichotomic subdivision process is made efficient by De Casteljau's algorithm. https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-sub.html; https://pdfs.semanticscholar.org/e8db/366b5a403d67fd265b64b3c6e24fbf4e04cb.pdf)

In addition, I guess that for polynomials of degree 30, numerical instabilities will creep in.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .