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,\dots$, of degree $n=2^k-1$ recursively defined by $p_1(x)=x+1$, $p_k(x)=x{p}_{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 $\underset{i\ne j}{min}|{\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 , DOI: 10.1553/etna_vol61s1

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