Answers are grounded in this paper and cite their sources.
This paper deals with the problem of numerically computing the roots of polynomials pₖ(x), k=1,2,…, of degree n=2ᵏ-1recursively defined by p₁(x)=x+1, pₖ(x)=xpₖ₋₁(x)²+1. An algorithm based on the Ehrlich-Aberth simultaneous iterations complemented by the Fast Multi-pole Method (FMM) and the fast search of near neighbors of a set of complex numbers is provided. The algorithm, which relies on a specific strategy of selecting initial approximations, costs O(nlog n) arithmetic operations per step. A Fortran 95 implementation is given and numerical experiments are carried out.Experimentally, it turns out that the number of iterations needed to arrive at numerical convergence is O(log n). This allows us to compute the roots of pₖ(x) up to degree n=2²⁴-1 in about 16 minutes on a laptop with 16 GB RAM, and up to degree n=2²⁸-1 in about 69 minutes on a machine with 256 GB RAM. The case of degree n=2³⁰-1 would require more memory and higher precision to separate the roots. With a suitable adaptation of the FMM to the limit of 256 GB RAM and by performing the computation in extended precision (i.e. with 10-byte floating point representation) we were able to compute all the roots in about two weeks of CPU time for n=2³⁰-1.From the experimental analysis, explicit asymptotic expressions of the real roots of pₖ(x) and an explicit expression of mini≠ j|ξᵢ⁽ᵏ⁾-ξⱼ⁽ᵏ⁾| for the roots ξᵢ⁽ᵏ⁾ of pₖ(x) are deduced. The approach is effectively applied to general classes of polynomials defined by a doubling recurrence.
No takes yet. Share an insight, caveat, or question.
Dario A. Bini (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: