Dierk Schleicher

We construct combinatorial Hubbard trees for all unicritical polynomials, and for all exponential maps, for which the critical (singular) value does not escape. More precisely, out of an external angle, or more generally a kneading sequence, we construct a forward invariant tree for which the critical orbit has the given kneading sequence. When the critical orbit of a unicritical polynomial is periodic or preperiodic, then the existence of a Hubbard tree is classical. Our trees exist even when the critical orbit is infinite (in many cases, this yields infinite trees), and even when the polynomial Julia set fails to be path connected. In the latter case, our trees cannot be reconstructed from the Julia set in complex dynamics. Our trees also exist for kneading sequences that do not arise in complex dynamics (for non complex-admissible kneading sequences).

We investigate Newton’s method as a root finder for complex polynomials of arbitrary degrees. While polynomial root finding continues to be one of the fundamental tasks of computing, with essential use in all areas of theoretical mathematics, numerics, computer graphics and physics, known methods may have excellent theoretical complexity but cannot be used in practice, or are practically efficient but lack a successful theory behind them. We provide precise and strong upper bounds for the theoretical complexity of Newton’s method and show that it is near-optimal with respect to the known set of starting points that find all roots. This theoretical result is complemented by a recent implementation of Newton’s method that finds all roots of various polynomials of degree more than a billion, significantly faster than our upper bounds on the complexity indicate, and often much faster than established fast root finders. Newton’s method thus stands out as a method that has strong merits both from the theoretical and from the practical point of view. Our study is based on the known explicit set of universal starting points, for each degree d, that are guaranteed to find all roots of polynomials of degree d (appropriately normalized). We show that this set contains d points that converge very quickly to the d roots: the expected total number of Newton iterations required to find all d roots with precision ɛ is O ( d 3  log 3 d + d  log  |  log  ε | ) , which can be further improved to O ( d 2  log 4 d + d  log  |  log  ε | ) . The key argument shows that many root finding orbits are ‘R-central’ in the sense that they stay forever in a disk of radius R, and each iteration ‘uses up’ an explicit amount A n , k ( ℓ ) of area within this disk.

Finding roots of univariate polynomials is one of the fundamental tasks of numerics, and there is still a wide gap between root finders that are well understood in theory and those that perform well in practice. We investigate the root-finding method of Weierstrass, also known as the Durand–Kerner-method: this is a root finder that tries to approximate all roots of a given polynomial in parallel. This method has been introduced 130 years ago and has since then a good reputation for finding all roots in practice except in obvious cases of symmetry. Nonetheless, very little is known about its global dynamics and convergence properties. We show that the Weierstrass method, like the well-known Newton method, is not generally convergent: there are open sets of polynomials p p of every degree d ≥ 3 d \ge 3 such that the dynamics of the Weierstrass method applied to p p exhibits attracting periodic orbits. Specifically, all polynomials sufficiently close to Z 3 + Z + 175 Z^3 + Z + 175 have attracting cycles of period 4 4 . Here, period 4 4 is minimal: we show that for cubic polynomials, there are no periodic orbits of length 2 2 or 3 3 that attract open sets of starting points. We also establish another convergence problem for the Weierstrass method: for almost every polynomial of degree d ≥ 3 d\ge 3 there are orbits that are defined for all iterates but converge to ∞ \infty ; this is a problem that does not occur for Newton’s method. Our results are obtained by first interpreting the original problem coming from numerical mathematics in terms of higher-dimensional complex dynamics, then phrasing the question in algebraic terms in such a way that we could finally answer it by applying methods from computer algebra. The main innovation here is the translation into an algebraic question, which is amenable to (exact) computational methods close to the limits of current computer algebra systems.

The dynamical classification of rational maps is a central concern of holomorphic dynamics. Much progress has been made, especially on the classification of polynomials and some approachable one-parameter families of rational maps; the goal of finding a classification of general rational maps is so far elusive. Newton maps (rational maps that arise when applying Newton's method to a polynomial) form a most natural family to be studied from the dynamical perspective. Using Thurston's characterization and rigidity theorem, a complete combinatorial classification of postcritically finite Newton maps is given in terms of a finite connected graph satisfying certain explicit conditions.

Thurston introduced invariant (quadratic) laminations in his 1984 preprint as a vehicle for understanding the connected Julia sets and the parameter space of quadratic polynomials. Important ingredients of his analysis of the angle doubling map $\sigma _2

This paper constructs a combinatorial model for all postcritically finite rational maps arising as the Newton's method of a complex polynomial. This model is used in [LMS] to give a combinatorial classification of postcritically finite Newton maps of any degree.