# Computing roots of high degree polynomial numerically.

Here is my problem ; for my research, I believe that the complex numbers I am looking at are precisely the (very large) set of roots of some high degree polynomial, of degree $\sim 2^n$ where $1 \le n \le 10 \sim 15$. Mathematica has been running for the whole day on my computer just for $2^{10}$ even though $2^9$ took half an hour, and I wondered if any other program out there would be faster than Mathematica so that I could compute more of those roots. If I had more examples to compute it would REALLY help. The thing I need the program to be able to do is simple : I give you a polynomial of very high degree, and I want to numerically plot its complex roots. I don't care about multiplicity.

EDIT: Marvis, here is my code for computing the nested polynomial $p^m(x) - x$, where $p^2(x) = p(p(x))$.

function r = polycomp(p,q);

r = p(1);

for k = 2:length(p);

r = conv(r,q);

r(end) = r(end) + p(k);

end

All I do afterwards is a loop with

r = [1 0]

for i = 1:n

r = polycomp(r,p)

end

where $n$ is my loop length and $p$ is my polynomial.

-
Have you tried using MATLAB? If not, try and use the command roots mathworks.com/help/techdoc/ref/roots.html. I tried for polynomial of degree 2000 and it took around a minute on my computer. – user17762 Jun 23 '12 at 16:39
@Marvis : Seriously? Man that is WAY faster than Mathematica! I didn't expect MATLAB would be so good. – Patrick Da Silva Jun 23 '12 at 16:47
@Marvis : Do you know any command in MATLAB allowing the "nesting" of polynomials? I don't expect this is a computational problem but to compute my polynomial I know it has the form $p(p(p(p(...(x))...)$ for a quadratic $p$, so it is unlikely I actually know the coefficients myself of the polynomial I am looking for.. – Patrick Da Silva Jun 23 '12 at 16:50
I have not solved polynomials in MATLAB so I am not much aware of solving polynomials. But I was wondering if you wanted to solve say $p(p(x)) = 0$, won't it be better to solve $p(y^*) = 0$ and then solve $p(x) = y^*$? You can then do this recursively. If you do it this way, you do not need to compute the coefficients. This is just a suggestion and I am not completely sure if this a better way to go. – user17762 Jun 23 '12 at 16:56
Actually I am solving $p(p(...p(x)...)) = x$, so no, a nesting is really not to be expected. – Patrick Da Silva Jun 23 '12 at 17:07

The MATLAB command roots() seems to do a fine job and at a decent speed. I tried using roots for polynomials of degree from $2^7$ to $2^{14}$ and below are the timings. The time for computing the roots using roots() seem to scale as $N^{\log_2(5)}$.

-
Thanks for everything. But now I am facing a new problem to go above $2^{13}$ (although I am VERY HAPPY to have gotten there! I have beautiful graphs I can conjecture at now.) The problem is I can't compute, say Nest[p,x,14] - x precisely enough. If the coefficients are integers, they go to MATLAB's infinity : if they are all $|a|,|b|,|c|< 1$ for say $ax^2 + bx + c$, then they go to zero too fast, and become NaN's. I have approximately your specs, but I am not worried about the time it takes, because I can wait (as long as its reasonable time, say a day or less... I only have one life left!) – Patrick Da Silva Jun 23 '12 at 20:04
How do you compute the coefficients of the final polynomial? I am wondering if there is any trick we can do to avoid computing these large coefficients in the first place... – user17762 Jun 23 '12 at 20:14
Well I can show you my code if you want! Comments are bad for this. See my answer's edit – Patrick Da Silva Jun 23 '12 at 20:42

I'm coming to the conversation late, but I note that there is no discussion of the accuracy of the determined roots. Roots are highly sensitive to perturbations in the polynomial coefficients, i.e. numerical precision is a key determinant of root accuracy particularly for huge polynomials.

My question: MATLAB may be faster but is it more accurate than Mathematica? Did you check to see whether your $2^n$ roots aren't mostly wildly inaccurate?

-
I am not working on the problem relative to this question anymore, and I managed to compute the roots to sufficient precision to notice that the problem I was working on is not of interest. Still, thank you for answering. – Patrick Da Silva Jan 19 '13 at 10:20