Fastest way to find roots

Question

I'm working with generative polynomials, and would like to know if there is a faster way to calculate roots. Using the technique below I've managed to cut the time down significantly. However at n=35, it still takes about two and a half minutes to calculate roots. Does anyone know of any ways I could speed this up? The time per polynomial increases rather quickly, and I would like to be able to calculate up to n=50, and I do not have access to a very fast machine.

h = Compile[{{z, _Real}, {m, _Integer}}, 
Coefficient[Series[1/((1 + l t + z t^2)^2), {t, 0, m}], t^m]];
l = 6.0;
Do[{
roots = z /. {ToRules[Quiet[NRoots[h[z, n] == 0., z]]]},
Print[roots]
    }, {n, 2, 35}]

Answer 1

Why not use SeriesCoefficient?

coeff[l_,n_] = Assuming[n>0, SeriesCoefficient[1/((1+l t+z t^2)^2),{t,0,n}]];
coeff[l,n] //TeXForm

$\frac{\left(\sqrt{l^2-4 z}+l\right)^2 \left(n \sqrt{l^2-4 z}+2 \sqrt{l^2-4 z}-l\right) \left(-\frac{1}{2} \sqrt{l^2-4 z}-\frac{l}{2}\right)^n}{4 \left(l^2-4 z\right)^{3/2}}+\frac{2^{-n-2} \left(\sqrt{l^2-4 z}-l\right)^{n+2} \left(n \sqrt{l^2-4 z}+2 \sqrt{l^2-4 z}+l\right)}{\left(l^2-4 z\right)^{3/2}}$

Solving the roots of coeff[l,n] is pretty fast:

roots = Table[
    NSolve@coeff[6, n],
    {n,2,50}
];// AbsoluteTiming
roots[[;;5]]

{2.6551, Null}

{{{z -> 54.}}, {{z -> 24.}}, {{z -> 126.991}, {z -> 17.0091}}, {{z -> 45.8745}, {z -> 14.1255}}, {{z -> 229.135}, {z -> 28.2533}, {z -> 12.612}}}

Answer 2

It looks like you are creating a series and then picking off the m-most term, which is a polynomial in z, and finding where it is equal to zero, correct? Just compute the m-most term directly from Taylor series properties:

hh[m_] := (D[1/((1 + l t + z t^2)^2), {t, m}] /. t -> 0)/m!

Then do the Do[ ] loop.

Do[{roots = z /. {ToRules[NRoots[hh[n] == 0., z]]}, Print[roots]}, {n,2, 50}]

Timing[ ] gave me .03 seconds to do all 50. Same answer as yours to do 25, but yours took 2.13 seconds just to do 25 of them.

Answer 3

Answer to the answer of Carl Woll:

There are two issus with that solution. 1. With MMA version 8.0 NSolve does't find all roots. Applying Simplify solves that problem.

Compare

 Table[{n, {NSolve[coeff[6, n]] // Sort}}, {n, 2, 
    10}] // TableForm

with

 Table[{n, {NSolve[coeff[6, n] // Simplify] // Sort}}, {n, 2, 
   10}] // TableForm

2. Using NRoots instead of NSolve is up to 50 times faster. Compare

   (roots = 
      Table[{n, {NSolve[coeff[6, n] // Simplify] // Sort}}, {n, 2, 
         50}]); // Timing
   
   (*    {3.735, Null}   *)
   

with

  (roots2 = 
Table[{n, {{ToRules[NRoots[Simplify[coeff[6, n]] == 0, z]]} // 
    Sort}}, {n, 2, 50}]); // Timing

(*  {0.078, Null}    *)