Numerical Methods for Computing Roots of High Degree Polynomials

Question

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.

Thanks in advance,

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.

Answer 1

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)}$.