How to split a tera-polynomial

Source abstract

This article presents a new algorithm to compute all the roots of a given polynomial. The algorithm is based on the computation of discrete level lines that provide excellent starting points for the Newton method. It applies to any polynomial, provided a good upper bound for its critical values. As observed in [26] and in Section below, for the polynomials of interest for the Mandelbrot set, this bound is 2 for one family and 4 for the other. In practice, our algorithm can split them in time linear in the degree. This article is paired with a code library [30] that implements this algorithm. For polynomials of small degree whose roots can be represented using only common hardware arithmetic (floating point FP80 ), the implementation of our algorithm can be run from a laptop. It can split polynomials of degree ∼ 10 9 in a few hours-core while polynomials of degree ∼ 10 6 take only a few seconds. Using this library and about 723 000 hours-core on the HPC center ROMEO (Reims), we also have successfully found all hyperbolic centers of period at most 41 and all Misiurewicz–Thurston parameters whose period and pre-period sum up to 35 . Concretely, this task involves splitting a tera-polynomial, i.e. a polynomial of degree ∼ 10 12 , which is several orders of magnitude beyond the previous state of the art. It also involves dealing with the certifiability of our numerical results, which is an issue that we address in detail, both mathematically and along the production chain. The certified database is available to the scientific community [29]. We provide a complementary statistical analysis of the separation of the roots, which confirms that the usage of higher precision arithmetic at this scale is absolutely necessary.