2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hello, I'll try to dig up some of the references I have on this later. But: have you by any chance tried using Aberth's method on your polynomials (assuming mpmath supports it; I haven't been able to check)? $\endgroup$ – J. M. is a poor mathematician Jun 4 '16 at 14:59
  • $\begingroup$ There are basically no global convergence results for this method. As you state, it is a Newton's method for the equation system giving the coefficients in terms of symmetric polynomials of the zeros, so local convergence holds. It is also not hard to show that the image of $f$ is contained in the hyperplane $\sum z_j = \sum r_j$, so you can reduce the dimension by one. In this way, global convergence for quadratic polynomials is easy to analyze, but degree 3 or higher is completely open. (E.g., it is unknown if there can be other attractors besides permutations of the zeros.) $\endgroup$ – Lukas Geyer May 15 '18 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.