0
$\begingroup$

I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest worst-case complexity? This algorithm will be for a general purpose computer(Turing Machine).

$\endgroup$
2
$\begingroup$

The paper Computing Real Roots of Real Polynomials by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The CGAL library (in version 4.9) for example uses the method developed by Arno Eigenwillig in his PhD thesis Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs.

$\endgroup$
  • 4
    $\begingroup$ How do you find rational roots with this method? $\endgroup$ – Discrete lizard Feb 22 '17 at 7:36
1
$\begingroup$

If you only want to find all rational roots, you can simply use the rational root theorem. This theorem states that, given a polynomial $a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1x+a_0$, for any rational root $x=p/q$, where $p,q\in \mathbb N$ and $GCD(p,q)=1$, we have:

  • $p$ is a divisor of $a_0$ and
  • $q$ is a divisor of $a_n$.

So, one possible algorithm is to factorise $a_0$ and $a_n$ to get all possible $p,q$ and simply 'fill in' the combinations as a ratio to see if it is a root. This way, we find all possible roots. The complexity of the root finding is negligible to the factorisation, so the complexity of this method is the complexity of factorising $a_0$ and $a_n$, which will take a long time for large $a_0$ and $a_n$ (but is fast for small $a_0$ and $a_n$, independent of the rest of the equation!)

There is a speedup, however. If a root $p/q\in [a,b]$, this means that $p\in [aq,bq]$ and $q\in [p/b,p/a]$. If $a_0$ is small, but $a_n$ is large, we can find all divisors $p_i$ of $a_0$ and test for all integers in the range $[p_i/b,p_i/a]$ whether they divide $a_n$. If $a_n$ is large and $[a,b]$ not too big, this will be a lot faster than factoring $a_n$. This means that we only have to do one factorisation and can do it on the smallest of $a_0$ and $a_n$.

So, to get a complete overview of the worst case complexity for the methods described, define $a_{\max}=\max\{a_0,a_n\}$ and $a_{\min} = \min\{a_0,a_n\}$. Assume $b\geq a>1$ (another worst case exists when $a,b<1$, but that will have the same running time, only with $1/a$ and $1/b$). We will factor $a_{\min}$ and consider all it's divisors, of which there are $O(\log n)$ on average (The actual worst case upper bound is $\exp(O(\frac{\log n}{\log\log n}))$, but this factor will likely be dominated anyway, so I'd rather keep it simple. A derivation and more is given here).

All divisors of $a_{\min}$ are in the range $[1,\sqrt{a_{\min}}]$, so we do at most $\lceil (b-a)\sqrt{a_{\min}} \rceil$ divisor tests per factor of $a_\min$. Since we know that any factor of $n$ must be in $[1,\sqrt{n}]$, we have that $b-a\leq \sqrt{a_\max}$ to be useful (if not, replace $[a,b]$ by $[1,\sqrt{a_\max}]$). So, we do at most $\lceil \sqrt{a_{\min}a_\max} \rceil$ divisor tests. Testing whether a number is a divisor of $a_\max$ takes $O(\log a_\max)$ time, using the Euclidean algorithm.

Factoring $a_\min$ takes $O(F(a_\min))$, where $F(n):=\exp ((\log n)^{1/3}(\log \log n)^{2/3})$.

So, in total, this algorithm has a worst case complexity of $O(F(a_\min) + (b-a)\sqrt{a_\min}\log{a_\min}\log{a_\max})$ time. Since we can assume $(b-a)\leq a_\max$, the factoring is the only non-polynomial (in $a_\min$ or $a_\max$) part of this formula, so we get that the complexity is simply $O(F(a_\min))$.

I highly doubt that it is possible to find all rational roots within a range without factoring at least one of the coefficients, because that would mean (by the rational root theorem), that we have found a more efficient algorithm for factoring! In that case, the algorithm I gave is asymptotically optimal, as it is the cost of factoring the smallest of the coefficients $a_0$ and $a_n$.

$\endgroup$
  • $\begingroup$ If only $a_n$ or only $a_0$ is large (and therefore hard to factor), you might be able to prove numerically that solutions can't be too far away from 0 or too close to 0, so very large factors might not lead to a solution ever, and you can stop when you have small factors. $\endgroup$ – gnasher729 Feb 22 '17 at 13:56
  • $\begingroup$ @gnasher729 How does this observation relate to this problem or my answer? I have already shown that if only one of them is large, factoring the small number is sufficient to find all rational roots. It might be possible to get an early conclusion that a certain large number does not lead to a useable factor, but I doubt this is true in general. $\endgroup$ – Discrete lizard Feb 22 '17 at 14:49
  • $\begingroup$ "The complexity of the root finding is negligible to the factorisation" - Do you have justification for this? Enumerating all divisors of $n$ can take a lot longer than factoring $n$. $\endgroup$ – D.W. Feb 22 '17 at 17:57
  • $\begingroup$ @D.W. It can take longer, as there may be a lot divisors. Indeed, the number of divisors can be $O(n^{1/3})$, in which case that term could dominate. However, on average, the amount of divisors of $n$ is about $O(\log n)$, as stated in the referenced blogpost. Perhaps it is not entirely correct to claim this is the worst case complexity and better to say that it is worst case under this (completely reasonable imo) assumption. $\endgroup$ – Discrete lizard Feb 23 '17 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.