I've been using the mpmath library's (in Python) implementation of the Durand-Kerner method to find the roots of some "not small" polynomials (this is the polyroots function).
Typically my polynomials have degrees of around 500 to 10,000. When I get to about polynomial degree 1000 I notice the method kind of grinds to a halt and does not appear to be converging, even if I up the iterations to 5000. Well, the more "isolated" roots are found, but it has difficulty zeroing in on the clusters of large numbers of roots that are close together. In my case, most of the roots are in the unit disc, on a a set of Hausdorff dimension somewhere between 1.4 and 1.5.
I'm wondering what kind of global results there are on the convergence of Durand-Kerner? My understanding of the method is that it is a fairly restricted Newton-type method. You take the fundamental theorem of algebra expression:
$$z^n + a_{n-1} z^{n-1} + \cdots + a_2 z^2 + a_1 z + a_0 = (z-r_1)(z-r_2)\cdots(z-r_n)$$
and you interpret it as a formula for the coefficients $a_k$ in terms of the roots $r_i$. You then apply the multi-variable Newton's method to solve for the roots, given the coefficients.
This means we are applying the multi-variable Newton method to find the (unique up to permutation) zero of the function:
$$f : \mathbb C^n \to \mathbb C^n $$ given by $$f \pmatrix{r_1 \cr r_2 \cr . \cr . \cr r_{n-1} \cr r_n} = \pmatrix{(-1)^nr_1r_2 \cdots r_{n-1}r_n \cr (-1)^{n-1} \sum_{i=1}^n r_1r_2\cdots \hat r_i \cdots r_{n-1}r_n \cr . \cr . \cr \sum_{i<j} r_ir_j \cr -\sum_{i=1}^n r_i } - \pmatrix{a_0 \cr a_1 \cr . \cr . \cr a_{n-2} \cr a_{n-1}} $$ where the $\hat r_i$ means an omitted variable.
I'm curious what kinds of convergence results there are for this method? I'm especially interested in global results. Certainly $Df$ is degenerate at many points, so the method has to fail for a decent amount of starting values. But is its dynamics as well-understood as the single-variable Newton method, say, for the roots of $z^3-1$ in the complex plane?