5
$\begingroup$

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.

  • 0
    Perhaps you could also try something like this, where you plot the whole function in such a way that it's visually clear where the zeros are: http://www.mai.liu.se/~halun/complex/domain_coloring-unicode.html#fig:iterates2012-06-24

2 Answers 2

2

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)}$. enter image description hereenter image description here

  • 0
    Well I can show you my code i$f$ you want! Comments are bad for this. See my answer's edit2012-06-23
1

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?

  • 0
    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.2013-01-19