Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
show 8 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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