Volume 61, pp. 1-27, 2024.
Numerical computation of the roots of Mandelbrot polynomials: an experimental analysis
Dario A. Bini
Abstract
This paper deals with the problem of numerically computing the roots of polynomials $p_k(x)$, $k=1,2,\ldots$, of degree $n=2^k-1$ recursively defined by $p_1(x)=x+1$, $p_k(x)=xp_{k-1}(x)^2+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(n\log 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_k(x)$ up to degree $n=2^{24}-1$ in about 16 minutes on a laptop with 16 GB RAM, and up to degree $n=2^{28}-1$ in about 69 minutes on a machine with 256 GB RAM. The case of degree $n=2^{30}-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^{30}-1$. From the experimental analysis, explicit asymptotic expressions of the real roots of $p_k(x)$ and an explicit expression of $\min_{i\ne j}|\xi_i^{(k)}-\xi_j^{(k)}|$ for the roots $\xi_i^{(k)}$ of $p_k(x)$ are deduced. The approach is effectively applied to general classes of polynomials defined by a doubling recurrence.
Full Text (PDF) [1.6 MB], BibTeX
Key words
Mandelbrot polynomials, polynomial roots, Ehrlich-Aberth iteration, fast multipole method
AMS subject classifications
65H04, 37F10, 30C15
Links to the cited ETNA articles
| [9] | Vol. 54 (2021), pp. 581-609 Difeng Cai and Jianlin Xia: A stable matrix version of the fast multipole method: stabilization strategies and examples |
Additional resources for this document
| Additional files |
< Back