Find roots of polynomial with degree $\ge 5$

Question

During our research we came up with the problem of computing the root of a polynomial of degree $\ge 5$ exactly. The coefficients are, except for the linear and constant term, all non-negative and there are only terms with even degree. The only thing we know is that there formulas for a degree up to 4 and no formula for a higher degree, but is it possible to compute the roots of a higher-degree polynomial exactly, too? If so, what is the complexity?

Here is some more information:

The equation looks like $A(n) - x - a_0 = 0$ for some arbitrary integral $n$. Thereby, $A(0)=x$ and $A(i) = a_i \cdot A(i-1) \cdot (A(i-1)+b_i) $ for $i \in \{1,\ldots,n\}$. All the values $a_i,b_i$ are non-negative real numbers for $i \in \{1,\ldots,n\}$ whereas $a_0$ is arbitrary.

Answer 1

If all the terms have even degree, you have a polynomial in $x^2$. Written that way, you have a polynomial of half the degree. This solves your problem if the original degree is $8$ or less. Otherwise, some polynomials of higher degree can be factored, giving exact roots. The rational root theorem can be your friend. Unless that is the case, you are out of luck.

Answer 2

Exactly? Depends on the polynomial. Note that for a polynomial of even degree, the substitution $y = x^2$ halves the degree of the polynomial, so for instance if the polynomial is degree six or eight, you can find its roots in closed form.

Otherwise, your only hope for exact roots (when the coefficients are rational) is that the polynomial has some special form, or factors. Linear factors can be extracted easily using the Rational Root Test. I'm sure more sophisticated algorithms exist that can be used to attempt to pull out higher-degree factors.

Lastly, if you just need the roots approximately, I will repeat my usual recommendation of the Jenkins-Traub algorithm -- the best numerical algorithm, in my experience, for finding all of the roots of a polynomial with a high degree of efficiency and accuracy.