Root Radii and Subdivision for Polynomial Root-Finding

Abstract

We depart from our approximation of 2000 of all root radii of a polynomial, which has readily extended Schönhage’s efficient algorithm of 1982 for a single root radius. We revisit this extension, advance it, based on our simple but novel idea, and yield significant practical acceleration of the known near optimal subdivision algorithms for complex and real root-finding of user’s choice. We achieve this by means of significant saving of exclusion tests and Taylor’s shifts, which are the bottleneck of subdivision root-finders. This saving relies on our novel recipes for the initialization of root-finding iterations of independent interest. We demonstrate our practical progress with numerical tests, provide extensive analysis of the resulting algorithms, and show that, like the preceding subdivision root-finders, they support near optimal Boolean complexity bounds.

Victor’s work is supported by NSF Grants CCF 1563942 and CCF 1733834 and PSC CUNY Award 63677 00 51.

1 Introduction

Overview. The recent subdivision iterations for univariate polynomial Complex Root Clustering (CRC) and Real Root Isolation (RRI) approximate all roots in a fixed Region of Interest (RoI) and, like the algorithm of Pan (1995, 2002), achieve near optimal bit complexity for the so called benchmark problem. Furthermore they allow robust implementations, one of which is currently the user’s choice for solving the RRI problem, including the task of the approximation of all real roots. Another implementation, for the CRC problem, is slower by several orders of magnitude than the package MPSolve (the user’s choice) for the task of finding all complex roots. However it outperforms MPSolve for solving the CRC problem where the RoI contains only a small number of roots. We significantly accelerate these highly efficient root-finding iterations by applying our novel techniques for their initialization. Next we specify the background and outline our contributions.

Polynomial Roots and Root Radii. For a polynomial $P$ of degree $d$ in $\mathbb Z[z]$ and a Gaussian integer $c\in \mathbb G{:=\{a+{\mathbf{i}}b ~|~ a\in \mathbb Z, b\in \mathbb Z\}}$, let $\alpha _1(P,c),\ldots ,\alpha _{d}(P,c)$ be the $d$ non-necessarily distinct roots of $P$ such that

$$\begin{aligned} |\alpha _1(P,c)-c|\ge |\alpha _2(P,c)-c| \ge \ldots \ge |\alpha _{d-1}(P,c)-c|\ge |\alpha _{d}(P,c)-c|. \end{aligned}$$

(1)

For all $1\le i\le d$, write $r_i(P,c):= |\alpha _i(P,c)-c|$, $\alpha _i(P):=\alpha _i(P,0)$ and $r_i(P):=r_i(P,0)$, so that

$$\begin{aligned} r_1(P,c)\ge r_2(P,c) \ge \ldots \ge r_{d-1}(P,c)\ge r_{d}(P,c). \end{aligned}$$

(2)

Then

$\rho _{c,1},\ldots ,\rho _{c,d}$ of Eq. (3) for fixed $c\in \mathbb G$ and $\delta >0$ define $d$ possibly overlaping concentric annuli. The connected components of their union form a set $\mathcal {A}_c$ of $d_c\le d$ disjoint concentric annuli centered at c. They cover all roots of $P$ and are said to be an annuli cover of the roots of $P$. We are going to use them in subdivision root-finding iterations.

Two Root-Finding Problems. We count roots with multiplicity and consider discs $D(c,r):=\{z ~|~ |z-c|\le r\}$ on the complex plane. For a positive $\delta$ let $\delta \Delta$ and $\delta B$ denote the concentric $\delta$-dilation of a disc $\Delta$ and a real line segment (i.e. interval) B. Then

It is quite common to pre-process $P\in \mathbb Z[z]$ in order to make it square-free, with $m^j=1$ for all j, but we do not use this option. We can state both CRC and RRI problems for $P$ with rational coefficients and readily reduce them to the above versions with integer coefficients by scaling.

Write $\Vert P\Vert :=\Vert P\Vert _\infty$ and call the value $\log _2\Vert P\Vert$ the bit-size of $P$.

The Benchmark Problem. For the bit-complexity of the so called benchmark root-finding problem of the isolation of all roots of a square-free $P\in \mathbb Z[z]$ of degree $d$ and bit-size $\tau$ the record bound of 1995 [13] is $\widetilde{O}(d^2(d+\tau ))$, near optimal for $\tau >d$ and based on a divide and conquer approach. It was reached again in 2016 [1, 2], based on subdivision iterations and implemented in [8].

Our Contributions. We first present and analyze an algorithm SolveRRC  that solves the RRC problem for polynomials with integer coefficients and any fixed center $c\in \mathbb G$. Our algorithm is adapted from work [12] (which has extended Schönhage’s highly efficient approximation of a single root radius in [15]) to simultaneous approximation of all $d$ root radii. Our specialization of this root radii algorithm to the case of integer polynomials and our analysis of its bit-complexity are novel. We use SolveRRC  for $\delta \in d^{-O(1)}$ and $|c|\in O(1)$; under such assumptions, it solves the RRC problem with a bit-complexity in $\widetilde{O}(d^2(d+ \tau ))$.

We then improve solvers for the RRI and the CRC problems based on subdivision with annuli covers that we compute by applying SolveRRC. The complexity of subdivision root-finders is dominated at its bottleneck stages of root-counting and particularly exclusion tests, at which costly Taylor’s shifts, aka the shifts of the variable, are applied. We significantly accelerate the root-finders for both RRI and CRC problems by means of using fewer exclusion tests and calls for root-counting and hence fewer Taylor’s shifts. We achieve this by limiting complex root-finding to the intersection of three annuli covers of the roots centered in 0, 1 and ${\mathbf{i}}$ and by limiting real root-finding to the intersection of a single annuli cover centered in 0 with the real line.

Table 1. Runs of Risolate, RisolateR, Ccluster and CclusterR on two polynomials. Ccluster and CclusterR are called with input $\varepsilon =2^{-53}$.

Our improvements are implemented within the C library Ccluster¹ which provides an eponymous solver for the CRC problem and a solver for the RRI problem called Risolate. Our novel solvers are called below CclusterR and RisolateR, and in Table 1 we overview how those two solvers perform against Ccluster and Risolate on a Bernoulli and a Mignotte polynomial. For each test polynomial we show its degree $d$, its bit-size $\tau$, and the number $d_\mathbb R$ of real roots. For each solver, t denotes the sequential running time in seconds on an Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz machine with Linux and n denotes the total number of Taylor’s shift required in the subdivision process. For CclusterR and RisolateR, $t'$ is the time spent on solving the RRC problem with SolveRRC.

We compute the annuli covers in a pre-processing step by applying algorithm SolveRRC for input relative width $\delta = 1/d^2$. This choice of $\delta$ is empiric, and in this sense our improvement of subdivision is heuristic. From a theoretical point of view, this allows our algorithms for solving the RRI and the CRC problems to support a near optimal bit-complexity. From a practical point of view, this allows us to significantly reduce the running time of solvers based on subdivision by using fewer Taylor’s shifts in exclusion and root-counting tests, as we highlighted in Table 1 (see the columns t and n).

The distance between roots of a polynomial of degree $d$ and bit-size $\tau$ can be way less than $1/d^2$ (see for instance [11]); thus by computing with SolveRRC intervals that contain the root radii of relative width $\delta = 1/d^2$, we do not intend to separate the roots of input polynomials, and our improvement has no effect in the cases where distances between some roots are less than $\delta$. We illustrate this in Table 1 for a Mignotte polynomial that has four real roots among which two roots have a pairwise distance that is close to the theoretical separation bound. Most of the computational effort in a subdivision solver for real roots isolation is spent on the separation of the close roots, and this remains true where we use annuli covers with relative width larger than the roots separation.

We compare our implementation with ANewDsc (see [10], implementing [14]) and MPSolve (see [3], implementing Ehrlich’s iterations), which are the current user’s choices for solving the RRI and the CRC problems, respectively.

Related Work. We departed from the subdivision polynomial root-finding for the CRC and RRI problems in [1] and [14], resp., and from the algorithms for the RRC problem in [15] (see [15][Cor. 14.3], and [5][Algorithm 2]) and [12]. We achieved practical progress by complementing these advanced works with our novel techniques for efficient computation of O(1) annuli covers of the roots. We rely on the customary framework for the analysis of root-finding algorithms and cite throughout the relevant sources of our auxiliary techniques.

Organization of the Paper. In Sect. 2 we describe an algorithm for solving the RRC problem. In Sects. 3 and 4 we present our algorithms for solving the RRI and CRC problem, respectively. In Subsect. 1.1 we introduce definitions. In Subsect. 1.2 we briefly describe the subdivision algorithm for the CRC problem of [1] and its adaptation to the solution of the RRI problem.

1.1 Definitions

Write $P:=P(z) := P_d\prod _{i=1}^{d} (z- \alpha _i(P)) = \sum _{j=0}^{d} P_j z^j$.

Root Squaring Iterations. For a positive integer $\ell$ write

$$\begin{aligned} {P}^{[\ell ]} := (P_d)^{2^\ell } \prod _{i=1}^{d} (z- \alpha _{i}(P)^{2^\ell }) \end{aligned}$$

(4)

and so ${P}^{[0]} = P$, ${P}^{[\ell ]} = {({P}^{[\ell -1]})}^{[1]}$ for $\ell \ge 1$, and

$$\begin{aligned} |\alpha _1( {P}^{[\ell ]} )|\ge |\alpha _2( {P}^{[\ell ]} )| \ge \ldots \ge |\alpha _{d-1}( {P}^{[\ell ]} )|\ge |\alpha _{d}( {P}^{[\ell ]} )|. \end{aligned}$$

(5)

${P}^{[\ell ]}$ is called the $\ell$-th root squaring iteration of $P$, aka the $\ell$-th Dandelin-Lobachevsky-Gräffe (DLG) iteration of $P$.

Write ${P}^{[\ell -1]}=\sum _{j=0}^{d} ({P}^{[\ell -1]})_j z^j$, ${P}^{[\ell -1]}_e=\sum _{j=0}^{\lfloor \frac{d}{2}\rfloor } ({P}^{[\ell -1]})_{2j} z^j$ and ${P}^{[\ell -1]}_o=\sum _{j=0}^{\lfloor \frac{d-1}{2}\rfloor } ({P}^{[\ell -1]})_{2j+1} z^j$. ${P}^{[\ell ]}$ can be computed iteratively based on the formula:

$$\begin{aligned} {P}^{[\ell ]} = (-1)^d \left[ ({P}^{[\ell -1]}_{e})^2 - z({P}^{[\ell -1]}_{o})^2 \right] . \end{aligned}$$

(6)

The j-th coefficient $({P}^{[\ell ]})_j$ of ${P}^{[\ell ]}$ is related to the coefficients of ${P}^{[\ell -1]}$ by:

$$\begin{aligned} ({P}^{[\ell ]})_j = (-1)^{d-j}({P}^{[\ell -1]})_j^2 + 2\sum _{k=\max (0,2j-d)}^{j-1} (-1)^{d-j}({P}^{[\ell -1]})_k({P}^{[\ell -1]})_{2j-k} \end{aligned}$$

(7)

$\boldsymbol{L}$-bit Approximations. For any number $c\in \mathbb C$, we say that $\widetilde{c}\in \mathbb C$ is an L-bit approximation of c if $\Vert \widetilde{c}-c\Vert \le 2^{-L}$. For a polynomial $P\in \mathbb C[z]$, we say that $\widetilde{P}\in \mathbb C$ is an L-bit approximation of $P$ if $\Vert \widetilde{P}-P\Vert \le 2^{-L}$, or equivalently if $\Vert \widetilde{P_j}-P_j\Vert \le 2^{-L}$ for all j.

Boxes, Quadri-Section, Line Segments, Bi-section. $[a-w/2, a+w/2] + {\mathbf{i}}[b-w/2, b+w/2]$ is the box B of width w centered at $c=a+{\mathbf{i}}b$. The disc $\Delta (B):=D(c,\frac{3}{4}w)$ is a cover of B.

Partition B into four congruent boxes (children of B), of width w/2 and centered at $(a\pm \frac{w}{4})+{\mathbf{i}}(b\pm \frac{w}{4})$.

$\Delta (B):=D(c,w/2)$ is the minimal disc that covers a real line segment $B:=[c-w/2, c+w/2]$ of width w centered at $c\in \mathbb R$.

Partition the segment B into two segments (children of B) of width w/2 centered at $(c\pm \frac{w}{4}))$.

Let $\mathcal {C}$ be a connected component of boxes (resp. real line segments); $B_{\mathcal {C}}$ is the minimal box (resp. real line segment) covering $\mathcal {C}$.

1.2 Subdivision Approach to Root-Finding

The work [1] describes an algorithm for solving a local version of the CRC problem: for an initial RoI $B_0$ (a box) it finds clusters of roots with pairwise distance less than $\varepsilon$ in a small inflation of $B_0$. Since our CRC problem is for input polynomials in $\mathbb Z[z]$, one can define a RoI containing all the roots by using, for instance, the Fujiwara bound (see [4]).

Subdivision Iterations. The algorithm in [1] uses subdivision iterations or Quad-tree algorithms (inherited from [7], see also [12]), which constructs a tree rooted in the RoI $B_0$ whose nodes are sub-boxes of $B_0$. A node B is included only if 2B contains a root, excluded only if it contains no root. A node is active if it is neither included nor excluded. At the beginning of a subdivision iteration, each active node B is tested for exclusion. Then active boxes are grouped into connected components, and for each connected component $\mathcal {C}$ such that $4\Delta (B_{\mathcal {C}})$ intersect no other connected component, a root-counter is applied to $2\Delta (B_{\mathcal {C}})$. If $2\Delta (B_{\mathcal {C}})$ contains $m>0$ roots and $\Delta (B_{\mathcal {C}})$ has radius less than $\varepsilon$, then $(\Delta (B_{\mathcal {C}}),m)$ is returned as a solution and the boxes of $\mathcal {C}$ are marked as included. Each remaining active node is quadrisected into its four active children, to which a new subdivision iteration is applied. Incorporation of Newton’s iterations enables quadratic convergence toward clusters of radii $\varepsilon$.

Solving the RRI Problem. Using a root separation lower bound (e.g., of [11]), one can derive from [1] a solution of the RRI problem based on the symmetry of roots of $P\in \mathbb Z[z]$ along the real axis. Let disc D(c, r) with $c\in \mathbb R$ contain m roots of $P$. For $m=1$ the root in D(c, r) is real. If $m\ge 1$ and $r\le \text {sep}(P)$, then D(c, r) contains a real root of multiplicity m, where $\text {sep}(P)$ is a root separation lower bound for $P$. For the RRI problem, the RoI $B_0$ is a line segment, and the subdivision tree of $B_0$ is built by means of segment bisection.

The $\boldsymbol{T^0}$ and $\boldsymbol{T^*}$ Tests. In the algorithm of [1], the exclusion test and root counter are based on Pellet’s theorem (see [2]). For a disc $\Delta =D(c,r)$, the counting test $T^*(\Delta ,P)$ returns an integer $k\in \{-1,0,\ldots ,d\}$ such that $k\ge 0$ only if $P$ has k roots in $\Delta$. A result $k=-1$ accounts for a failure and holds when some roots of $P$ are close to the boundary of $\Delta$. For a given disc $\Delta$, the exclusion test $T^0(\Delta ,P)$ returns 0 if $T^*(\Delta ,P)$ returns 0 and returns $-1$ if $T^*(\Delta ,P)$ returns a non-zero integer. The $T^*$ of [2] takes as an input an L-bit approximation of $P$ and with working absolute precision L performs about $\log \log d$ DLG iterations of the Taylor’s shift $P(c+rz)$ of $P$. Write $L(\Delta ,P)$ for the precision L required to carry out the $T^*$-test. Based on Pellet’s theorem we obtain the following results.

Proposition 1

(see [2], Lemmas 4 and 5). Let B be the box (or real line segment) centered in c with width w. The total cost in bit operations for carrying out $T^*(\Delta (B),P)$ or $T^0(\Delta (B),P)$ is bounded by

$$\begin{aligned} \widetilde{O}( d( \log \Vert P\Vert + d\log \max (1,|c|,w) + L(\Delta ,P))). \end{aligned}$$

(8)

$T^*(\Delta (B),P)$ returns an integer $k\in \{ -1,0,\ldots ,d\}$; if $k\ge 0$ then $\Delta (B)$ contains k roots; if $k=-1$ then $P$ has a root in $2B\setminus (1/2)B$. $T^0(\Delta (B),P)$ returns an integer $k\in \{ -1,0\}$; if $k = 0$ then $P$ has no root in $\Delta (B)$; if $k=-1$ then $P$ has a root in 2B.

Bit Complexity. Proposition 1 enables one to bound the Boolean cost of exclusion tests and root-counting as well as the size of the subdivision tree and hence the cost of solving the benchmark problem in [1].

By applying subdivision iterations with an exclusion test and a root counter satisfying Proposition 1 one yields an algorithm with the same bit-complexity as the algorithm of [1], namely, $\widetilde{O}(d^2(d+\tau ))$ for the benchmark problem.

Implementations. A modified version of [1] for the CRC problem has been implemented and made public within the library Ccluster. An implementation of the modified algorithm of [1] solving the RRI problem, called Risolate, is also available within Ccluster.

2 Root Radii Computation

We describe and analyse an algorithm for solving the RRC problem for a $P\in \mathbb G[z]$. Let $c\in \mathbb G$ and ${P}{c} (z):=P(c+z)$, so that $r_s(P,c)=r_s( {P}{c} )$ for all $1\le s\le d$. Hence the RRC problem for a $c\ne 0$ reduces to the RRC problem for $c=0$ at the cost of shifting the variable.

The next remark reduces the RRC problem for $c=0$ and any $\delta >0$ to the RRC problem for $1+\delta =4d$ by means of DLG iterations:

Remark 2

Let $g=\lceil \log \dfrac{\log (4d)}{\log (1+\delta )}\rceil$, let $\rho '>0$ such that there exist an s with:

$$\begin{aligned} \frac{\rho '}{4d}< r_s({ {P}{c} }^{[g]}) < (4d)\rho '. \end{aligned}$$

(9)

Define $\rho =(\rho ')^{\frac{1}{2^g}}$ and recall that $r_s({ {P}{c} }^{[g]}) = r_s(P,c)^{2^g}$. Then

$$\begin{aligned} \frac{\rho }{1+\delta }< r_s(P,c) < (1+\delta )\rho . \end{aligned}$$

(10)

g is in $O(\log d)$ if $\delta$ is in $d^{-O(1)}$ (for instance, $\delta \ge d^{-1}$ or $\delta \ge d^{-2}$).

Now define the RRC$^*$ problem as the RRC problem for $1+\delta =4d$ and $c=0$:

In this setting, we assume that 0 is not a root of $P$ and thus $P_0\ne 0$. When 0 is a root of multiplicity m, then $r_d(P)=\ldots =r_{d-m+1}(P)=0$ and $P_0=\ldots =P_{m-1}=0$, which is easily detected (since $P\in \mathbb G[z]$) and treated accordingly.

In Subsect. 2.1 we recall an algorithm $\mathtt{SolveRRC^*}$ satisfying:

Proposition 3

Algorithm $\mathtt{SolveRRC^*}$ in Algorithm 1 solves the RRC$^*$ problem by involving $O(d\log \Vert P\Vert )$ bit operations.

In Subsect. 2.2 we prove this proposition. In Subsect. 2.3 we present an algorithm $\mathtt{SolveRRC}$ satisfying:

Theorem 4

The algorithm $\mathtt{SolveRRC}$ of Subsect. 2.3 solves the RRC problem for $\delta = d^{-2}$ at a Boolean cost in

$$\begin{aligned} \widetilde{O}( d^2(d\log (|c|+1) + \log \Vert P\Vert ) ). \end{aligned}$$

(12)

This bound turns into $\widetilde{O}( d^2(d+ \log \Vert P\Vert ) )$ for $|c| \in O(1)$ and into $\widetilde{O}( d^2\log \Vert P\Vert )$ for $|c|=0$.

Below we will use root radii computation as a pre-processing step for Complex Root Clustering and Real Root Isolation. For Real Root Isolation, we use $\mathtt{SolveRRC}$ to compute an annuli cover centered at 0. For Complex Root Clustering, we use $\mathtt{SolveRRC}$ to compute three annuli covers with the three centers $0, 1, {\mathbf{i}}$. According to our analysis of the RRC problem, the cost of its solution for O(1) centers c such that $|c|\in O(1)$ is dominated by a near optimal bit-complexity of root-finding.

For $c=0$, our algorithm has a larger bit complexity than the algorithm of [15] (see [15][Cor. 14.3] and [5][Algorithm 2]), which is in $\widetilde{O}(d^2\log ^2d)$ when $\log \Vert P\Vert \in O(d)$. Our algorithm, however, computes $d$ root radii at once where Schönhage’s algorithm computes only a single root radius. It is not clear whether the latter algorithm can be extended to an algorithm that would solve the RRC problem within the same bit-complexity bound.

2.1 Solving the RRC$^*$ Problem

Recall that $P=\sum _{i=0}^{d}P_iz^i$ and define, for $i=0,\ldots ,d$,

$$\begin{aligned} p_i = \left\{ \begin{array}{ll} \log |P_i| &{} \text { if } P_i\ne 0,\\ -\infty &{} \text { otherwise.} \end{array} \right. \end{aligned}$$

(13)

According to the following result, adapted from Proposition 4.2 and its proof in [12], one can solve the RRC$^*$ problem by computing the upper part of the convex hull of the set of points $\{ (i,p_i) | i=0,\ldots ,d\}$ and assuming that the points $(i,-\infty )$ lie below any line in the plane.

Proposition 5

Given an integer s, let $t'$ and $h'$ be integers s.t.

$(i')$:

$t'<d+1-s\le t'+h' \le d$, and

$(ii')$:

$\forall 0\le i \le d$, the point $(i,p_i)$ lies below the line $((t',p_{t'}), (t'+h',p_{t'+h'}))$.

Then $\rho _s'=\left| \dfrac{P_{t'}}{P_{t'+h'}}\right| ^{\frac{1}{h'}}$ satisfies: $\dfrac{\rho _s'}{2d}< r_s(P) < (2d)\rho _s'$.

Call CH the upper part of the convex hull of the points $\{ (i,p_i) | i=0,\ldots ,d\}$, and remark that for a given integer s, the integers $t'$ and $t'+h'$ satisfying $(i')$ and $(ii')$ in Proposition 5 are the abscissæ of the endpoints of the segment of CH above $(s,p_s)$. CH can be computed exactly (the $P_i$’s are Gaussian integers). However for solving the RRC$^*$ problem, it is sufficient to compute the upper part of the convex hull of M-bit approximations of the $p_i$’s with $M\ge 1$. For $i=0,\ldots ,d$, define

$$\begin{aligned} \widetilde{p_i}: = \left\{ \begin{array}{ll} M\text {-bit approximation of } p_i &{} \text { if } |P_i|>1,\\ 0 &{} \text { if } |P_i|=1,\\ -\infty &{} \text { otherwise}. \end{array} \right. \end{aligned}$$

(14)

Let $\widetilde{CH}$ be the upper part of the convex hull of $\{ (i,\widetilde{p_i}) | i=0,\ldots ,d\}$ and let points $(i,-\infty )$ lie below any line in the plane. Given an index s, the following proposition bounds the slope of the edge of CH above $d+1-s$ in terms of the slope of the edge of $\widetilde{CH}$ above $d+1-s$ and M.

Proposition 6

Given an integer s, let $t,h,t'$, and $h'$ be integers such that

(i):

$t<d+1-s\le t+h \le d$,

(ii):

$\forall 0\le i \le d$, the point $(i,\widetilde{p_i})$ lies below the line $((t,\widetilde{p_{t}}), (t+h,\widetilde{p_{t+h}}))$,

$(i')$:

$t'<d+1-s\le t'+h' \le d$, and

$(ii')$:

$\forall 0\le i \le d$, the points $(i,p_i)$ lie below the line $((t',p_{t'}), (t'+h',p_{t'+h'}))$.

Then

$$\begin{aligned} \dfrac{\widetilde{p_{t+h}}-\widetilde{p_{t}}}{h} - 2^{-M+1} \le \dfrac{p_{t'+h'}-p_{t'}}{h'} \le \dfrac{\widetilde{p_{t+h}}-\widetilde{p_{t}}}{h} + 2^{-M+1}. \end{aligned}$$

(15)

For a given integer s, the existence of integers $t,h,t',h'$ satisfying (i), (ii), $(i')$, $(ii')$ follows from the existence of the convex hulls CH and $\widetilde{CH}$. We postpone the proof of Proposition 6. Remark that $2^{2^{-L}} \le 1+2^{-L}$ for $L\ge 0$, apply Proposition 5, and obtain:

Corollary 7

(of Proposition 6). Let s, t, h be as in Proposition 6. Define $\widetilde{\rho _s}'$ as $\left| \dfrac{P_t}{P_{t+h}}\right| ^{\frac{1}{h}}$. Then

$$\begin{aligned} \frac{\widetilde{\rho _s}'}{(2d)(1+2^{-M+1})}< r_s(P) < (2d)(1+2^{-M+1})\widetilde{\rho _s}'. \end{aligned}$$

(16)

We are ready to describe our Algorithm 1, which solves the RRC$^*$ problem. In steps 1–2, 1-bit approximations $\widetilde{p_i}$ of $p_i=\log |P_i|$ are computed from $P_i$, for $i=0,\ldots ,d$. This requires $O(d\log \Vert P\Vert )$ bit operations. In step 3 we compute the convex hull $\widetilde{CH}$ of a polygon with $d+1$ vertices $(0,\widetilde{p_0}),\ldots , (d,\widetilde{p_d})$ ordered with respect to their ordinates. Using Graham’s algorithm of [6], we only need $O(d)$ arithmetic operations (additions) with numbers of magnitude $O(\log \Vert P\Vert )$. In steps 4,5,6, the $\widetilde{\rho _s}'$’s for $s=0,\ldots ,d$ are computed as in Corollary 7. This task is performed with rounding to double precision arithmetic and requires $O(d)$ bit operations. Finally, $(1+2^{-M+1})\le 2$ if $M\ge 1$; thus the $\widetilde{\rho _s}'$’s in the output satisfy $\forall s=1,\ldots ,d,~~\frac{\widetilde{\rho _s}'}{4d}< r_s(P) < (4d)\widetilde{\rho _s}',$ and Proposition 3 follows.

2.2 Proof of Proposition 6

Fig. 1.

The convex hulls CH and $\widetilde{CH}$ (Color figure online)

For $i=0,\ldots , d$, define $\widetilde{p_i}^+$ and $\widetilde{p_i}^-$ as

$$\begin{aligned} \widetilde{p_i}^+ = \left\{ \begin{array}{ll} \widetilde{p_i} + 2^{-M} &{} \text { if } |\widetilde{p_i}|> -\infty ,\\ -\infty &{} \text {otherwise} \end{array} \right. \text {, and } \widetilde{p_i}^- = \left\{ \begin{array}{ll} \widetilde{p_i} - 2^{-M} &{} \text { if } |\widetilde{p_i}|> -\infty ,\\ -\infty &{} \text {otherwise} \end{array} \right. . \end{aligned}$$

(17)

$\widetilde{CH}$ is the upper part of the convex hull of $\{ (i,\widetilde{p_i}) | i=0,\ldots ,d\}$. Suppose that it is the poly-line passing through $\{ (i_k,\widetilde{p_{i_k}}) | k=0,\ldots ,\ell \}$. It defines two poly-lines:

• $\widetilde{CH}^+$, the poly-line with vertices $\{ (i_k,\widetilde{p_{i_k}}^+ | k=0,\ldots ,\ell \}$, and

• $\widetilde{CH}^-$, the poly-line with vertices $\{ (i_k,\widetilde{p_{i_k}}^-) | k=0,\ldots ,\ell \}$.

CH is the upper part of the convex hull of $\{ (i,p_i) | i=0,\ldots ,d\}$, and suppose it is the poly-line with vertices $\{ (j_k,p_{j_k}) | k=0,\ldots ,\ell ' \}$. For demonstration see Fig. 1 where $d=8$, the $\widetilde{p_i}$’s are drawn with black circles, the intervals $[\widetilde{p_i}^-,\widetilde{p_i}^+]$ with bold vertical bars, $\widetilde{CH}$ with a bold blue poly-line, $\widetilde{CH}^+$ and $\widetilde{CH}^-$ with dashed blue poly-lines, and CH with a bold red line. One has:

Proposition 8

The poly-line CH lies below the poly-line $\widetilde{CH}^+$ and above the poly-line $\widetilde{CH}^-$.

Proof of Proposition 8: In order to prove that CH lies below $\widetilde{CH}^+$, we show that if $j_t, i_k, i_{k'}$ is a triple of integers such that $(j_t,p_{j_t})$ is a vertex of CH and $[ (i_k,\widetilde{p_{i_k}}^+), (i_{k'},\widetilde{p_{i_{k'}}}^+) ]$ is an edge of $\widetilde{CH}^+$, then $(j_t,p_{j_t})$ lies on or below the line $( (i_k,\widetilde{p_{i_k}}^+), (i_{k'},\widetilde{p_{i_{k'}}}^+) )$. Suppose this is not the case, i.e. the point $(j_t,p_{j_t})$ lies strictly above the line $( (i_k,\widetilde{p_{i_k}}^+), (i_{k'},\widetilde{p_{i_{k'}}}^+) )$. Since $p_{j_t}\le \widetilde{p_{j_t}}^+$, $\widetilde{p_{j_t}}^+$ lies strictly above $( (i_k,\widetilde{p_{i_k}}^+), (i_{k'},\widetilde{p_{i_{k'}}}^+) )$, thus $\widetilde{p_{j_t}}$ lies strictly above $( (i_k,\widetilde{p_{i_k}}), (i_{k'},\widetilde{p_{i_{k'}}}) )$ and $\widetilde{CH}$ is not the convex hull of $\{ (i,\widetilde{p_i}) | i=0,\ldots ,d\}$, which is a contradiction.

In order to show that $\widetilde{CH}^-$ lies below CH, we show that for a given triple of integers $i_t, j_k, j_{k'}$ such that $(i_t,\widetilde{p_{i_t}}^-)$ is a vertex of $\widetilde{CH}^-$ and $[ (j_k,p_{j_k}), (j_{k'},p_{j_{k'}}) ]$ is an edge of CH, the point $(i_t,\widetilde{p_{i_t}}^-)$ lies on or below the line $( (j_k,p_{j_k}), (j_{k'},p_{j_{k'}}) )$. Suppose it is not the case. Since $p_{i_t}\ge \widetilde{p_{i_t}}^-$, the point $p_{i_t}$ lies strictly above the line passing through $( (j_k,p_{j_k}), (j_{k'},p_{j_{k'}}) )$ and CH is not the convex hull of $\{ (i,p_i) | i=0,\ldots ,d\}$, which is a contradiction.    $\square$

Proof of Proposition 6: Given the integer s, let $t,h,t',h'$ be integers such that conditions $(i), (ii), (i')$ and $(ii')$ hold.

By virtue of $(i')$ and $(ii')$, $](t',p_{t'}), (t'+h',p_{t'+h'})]$ is the edge of CH whose orthogonal projection onto the abscissa axis contains $d+1-s$, and $\dfrac{p_{t'+h'} - p_{t'}}{h'}$ is the slope of that edge.

By virtue of (i) and (ii), $](t,\widetilde{p_{t}}), (t+h,\widetilde{p_{t+h}})]$ is the edge of $\widetilde{CH}$ whose orthogonal projection onto the abscissa axis contains $d+1-s$. Consider the two segments $](t,\widetilde{p_{t}}^-), (t+h,\widetilde{p_{t+h}}^-)]$ and $](t,\widetilde{p_{t}}^+), (t+h,\widetilde{p_{t+h}}^+)]$ that are the edges of $\widetilde{CH}^-$ and $\widetilde{CH}^+$, respectively, whose orthogonal projections onto the abscissa axis also contain $d+1-s$.

From Proposition 8 CH is a poly-line enclosed by $\widetilde{CH}^-$ and $\widetilde{CH}^+$ and since the first coordinates of its vertices are integers, its slope $\dfrac{p_{t'+h'} - p_{t'}}{h'}$ above $d+1-s$ is bounded below by $\dfrac{\widetilde{p_{t+h}} - \widetilde{p_{t}}}{h} - 2^{-M+1}$ and above by $\dfrac{\widetilde{p_{t+h}} - \widetilde{p_{t}}}{h} + 2^{-M+1}$, which proves Proposition 6. See Fig. 1 for an illustration.    $\square$

2.3 Solving the RRC Problem

Using Remark 2, we define in Algorithm 2 the algorithm $\mathtt{SolveRRC}$. To estimate the cost at steps 2 and 3, let $\mathcal {M}:\mathbb N\rightarrow \mathbb N$ be such that two polynomials of degree at most $d$ and bit-size at most $\tau$ can be multiplied by using $O(\mathcal {M}(d\tau ))$ bit operations. Recall the following:

• 1. computing ${P}{c}$ requires $O(\mathcal {M}(d^2\log d+ d^2\log (|c|+1) + d\log \Vert P\Vert ))$ bit operations,

• 2. $\Vert {P}{c} \Vert \le \Vert P\Vert (|c|+1)^d$,

• 3. computing $\Vert { {P}{c} }^{[i]}\Vert$ from $\Vert { {P}{c} }^{[i-1]}\Vert$ requires $O(\mathcal {M}(d\log \Vert { {P}{c} }^{[i-1]}\Vert ))$ bit operations,

• 4. $\Vert { {P}{c} }^{[i]}\Vert \le (d+1)(\Vert { {P}{c} }^{[i-1]}\Vert )^2\le \ldots \le (d+1)^{2^i}(\Vert {P}{c} \Vert )^{2^i}$.

For 1 and 2, see for instance [16][Theorem 2.4] and [16][Lemma 2.1]). 3 and 4 are derived from Eqs. (6) and (7), respectively. From 2, 4 and $g\in O(\log d)$ one obtains

$$\begin{aligned} \log \Vert { {P}{c} }^{[g]} \Vert \in O(d\log (d+1) + d\log \Vert P\Vert + d^2\log (|c|+1)), \end{aligned}$$

(18)

thus performing g DLG iterations for ${P}{c}$ involves

$$\begin{aligned} O(g\mathcal {M}(d\log \Vert { {P}{c} }^{[g]} \Vert )) = O(\log d\mathcal {M}(d(d\log (d+1) + d\log \Vert P\Vert + d^2\log (|c|+1)))) \end{aligned}$$

(19)

bit operations; this dominates the cost of step 2. Due to Schönhage-Strassen or Harvey-van der Hoeven multiplication, $\mathcal {M}(n)\in \widetilde{O}(n)$, and so step 2 involves

$$\begin{aligned} \widetilde{O}( d^2\log \Vert P\Vert + d^3\log (|c|+1)) \end{aligned}$$

(20)

bit operations. Step 3 involves $O(d\log \Vert { {P}{c} }^{[g]} \Vert )$ bit operations, the cost of the for loop in steps 4–5 is dominated by the cost of step 2, and we complete the proof of Theorem 4.

2.4 Implementation Details

The exact computation of ${ {P}{c} }^{[g]}$ can involve numbers of very large bit-size (see Eq. (18)), and the key point for the practical efficiency of our implementation of Algorithm 2 is to avoid this. Instead, we use ball arithmetic, i.e. arbitrary precision floating point arithmetic with absolute error bounds, implemented for instance in the C library arb (see [9]).

3 Real Root Isolation

In this section, we approximate the root distances to 0 in order to improve in practice subdivision approaches to real root isolation, and in particular the one described in Subsect. 1.2. Let us define the notion of annuli cover of the roots of $P\in \mathbb Z[z]$.

Definition 1

A set $\mathcal {A}_c$ of disjoint concentric annuli centered in c is an annuli cover of the roots of $P$ of degree $d$ if

• 1. $\forall A\in \mathcal {A}_c$, there are integers t(A) and h(A) such that

  $$\begin{aligned} \alpha _{t(A)}(P,c),\alpha _{t(A)+1}(P,c),\ldots ,\alpha _{t(A)+h(A)}(P,c)\in A, \end{aligned}$$

  (21)

• 2. $\forall i\in \{1,\ldots ,d\}$, there is an $A\in \mathcal {A}_c$ such that $\alpha _i(P,c)\in A$.

For an annulus $A\in \mathcal {A}_c$, $\underline{r}(A)$ and $\overline{r}(A)$ are the interior and exterior radii of A, respectively. Write $s_+(A):=P(c+\underline{r}(A))P(c+\overline{r}(A))$ and $s_-(A):=P(c-\underline{r}(A))P(c-\overline{r}(A))$.

Given an annuli cover $\mathcal {A}_0$ centered at 0, we can skip many calls for exclusion and root-counting based on the following:

Remark 9

Let $A\in \mathcal {A}_0$ such that $\underline{r}(A)>0$.

• 1. If $h(A)=0$ and $s_+(A)>0$ (resp. $s_-(A)>0$), $A\cap \mathbb R_+$ (resp. $A\cap \mathbb R_-$) contains no real root of $P$.

• 2. If $h(A)=0$ and $s_+(A)<0$ (resp. $s_-(A)<0$), $A\cap \mathbb R_+$ (resp. $A\cap \mathbb R_-$) contains one real root of $P$.

• 3. If $h(A)>0$ and $s_+(A)<0$ (resp. $s_-(A)<0$), $A\cap \mathbb R_+$ (resp. $A\cap \mathbb R_-$) contains at least one real root of $P$.

In Subsects. 3.1 and 3.2 we describe our exclusion test and root counter based on Remark 9. In Subsect. 3.3 we describe our algorithm solving the RRI problem. In Subsect. 3.4 we present the results of our numerical tests.

3.1 Annuli Cover and Exclusion Test

Let B be a real line segment that does not contain 0, let $\mathcal {A}$ be an annuli cover centered in 0, and let $A\in \mathcal {A}$. Define that:

• $s_B$, the sign of B, is $-1$ (resp. 1) if $B<0$ (resp. $B>0$),

• $\mathbb Rs_B(A)$ is $A\cap \mathbb R_-$ if $s_B<0$, and is $A\cap \mathbb R_+$ otherwise,

• $ss_B(A)$ is $s_-(A)$ if $s_B<0$, and is $s_+(A)$ otherwise,

• $n(\mathcal {A},B)$ is the number of annuli $A\in \mathcal {A}$ s.t. $A\cap B\ne \emptyset$,

• $n_0(\mathcal {A},B)$ is the number of annuli $A\in \mathcal {A}$ s.t.

  $$\begin{aligned} (A\cap B\ne \emptyset )\wedge (h(A)=0)\wedge ss_B(A)>0, \end{aligned}$$

  (22)

• $n_{\ge 1}(\mathcal {A},B)$: the number of annuli $A\in \mathcal {A}$ s.t.

  $$\begin{aligned} (A\cap B\ne \emptyset )\wedge (h(A)\ge 0)\wedge ss_B(A)<0 \wedge \mathbb Rs_B(A)\subseteq 2B. \end{aligned}$$

  (23)

By virtue of Remark 9, if $n(\mathcal {A},B)=n_0(\mathcal {A},B)$, then all the annuli intersecting B contain no root, thus B contains no root. If $n_{\ge 1}(\mathcal {A},B)\ge 1$ then 2B contains at least one real root.

Our exclusion test $C_\mathbb R^0$ is described in Algorithm 3. For computing $n(\mathcal {A},B)$, $n_0(\mathcal {A},B)$ and $n_{\ge 1}(\mathcal {A},B)$ in Step 1, we use double precision interval arithmetic, hence Step 1 involves $O(d)$ bit operations. This implies

Proposition 10

Let B be a real line segment with $0\notin B$, and let $\mathcal {A}$ be an annuli cover of the roots of $P$ centered in 0. The cost of carrying out $C_\mathbb R^0(B, P,\mathcal {A})$ is bounded by the cost of carrying out $T^0(\Delta (B), P)$.

$C_\mathbb R^0(B,P,\mathcal {A})$ returns an integer k in $\{-1,0\}$. If $k=0$, then $P$ has no real roots in B. If $k=-1$, then $P$ has a root in 2B.

3.2 Annuli Cover and Root Counter

In order to describe our root counter, we define:

• $n_1(\mathcal {A},B)$: the number of annuli $A\in \mathcal {A}$ s.t. :

  $$\begin{aligned} (A\cap B\ne \emptyset )\wedge (h(A)=0)\wedge (ss_B(A)<0) \wedge (\mathbb Rs_B(A)\subseteq B), \end{aligned}$$

  (24)

• $n_{\ge 1}'(\mathcal {A},B)$: the number of annuli $A\in \mathcal {A}$ s.t.:

  $$\begin{aligned} (~A\cap B\ne \emptyset )\wedge (h(A)\ge 0)\wedge ss_B(A)<0 \wedge (\mathbb Rs_B(A)\subseteq 2B\setminus (1/2)B~). \end{aligned}$$

  (25)

By virtue of Remark 9, if $n(\mathcal {A},B)=n_0(\mathcal {A},B)+n_1(\mathcal {A},B)$, B contains exactly $n_1(\mathcal {A},B)$ real roots. If $n_{\ge 1}'(\mathcal {A},B)\ge 1$ then $P$ has at least one real root in $2B\setminus (1/2)B$.

Our root counter is described in Algorithm 4. We use double precision interval arithmetic for computing $n(\mathcal {A},B)$, $n_0(\mathcal {A},B)$, $n_1(\mathcal {A},B)$ and $n_{\ge 1}'(\mathcal {A},B)$ in Step 1, thus Step 1 involves $O(d)$ bit operations.

Proposition 11

Let B be a real line segment with $0\notin B$ and let $\mathcal {A}$ be an annuli cover of the roots of $P$ centered in 0. The cost of carrying out $C_\mathbb R^*(B, P,\mathcal {A})$ is bounded by the cost of carrying out $T^*(\Delta (B), P)$.

$C_\mathbb R^*(B,P,\mathcal {A})$ returns an integer k in $\{-1,0,\ldots ,d\}$. If $k\ge 0$, then $P$ has k roots in $\Delta (B)$. If $k=-1$, then $P$ has a root in $2B\setminus (1/2)B$.

3.3 Annuli Cover and the RRI Problem

Consider the following procedure.

Stage 1: Compute $\mathcal {A}_0$ by calling $\mathtt{SolveRRC}(P,0,d^{-2})$.

Stage 2: Apply the subdivision procedure of Subsect. 1.2 while using $C_\mathbb R^0(B, P,$ $\mathcal {A}_0)$ (resp. $C_\mathbb R^*(B, P,\mathcal {A}_0)$) as an exclusion test (resp. root counter) for real line segment B of the subdivision tree. In the verification step of Newton iterations, use the $T^*$-test of [2].

At Stage 1, we obtain $\mathcal {A}_0$ by computing the connected components made up of the concentric annuli defined by the output of $\mathtt{SolveRRC}(P,0,d^{-2})$.

By virtue of Theorem 4 and Propositions 10 and 11, this procedure solves the RRI problem, and its bit-complexity is bounded by the bit-complexity of the algorithm described in [1], thus it is near optimal for the benchmark problem.

3.4 Experimental Results

The procedure given in Subsect. 3.3 has been implemented within the library Ccluster; we call this implementation RisolateR. Comparison of RisolateR with Risolate reveals practical improvement due to using our root radii algorithms in subdivision process. We also compare RisolateR with the subdivision algorithm of [14] whose implementation ANewDsc is described in [10] and is currently the user’s choice for real root isolation.

Test Polynomials. We consider the following polynomials.

The Bernoulli polynomial of degree $d$ is $B_d(z)=\sum _{k=0}^{d} {{d}\atopwithdelims (){k}}b_{d-k}z^k$ where the $b_i$’s are the Bernoulli numbers.

The Wilkinson polynomial of degree $d$ is $W_d(z) = \prod _{i=1}^d(z-i)$.

For integers $n>0$, we define polynomials with $(2n+1)\times (2n+1)$ roots on the nodes of a regular grid centered at 0 as

$$\begin{aligned} P_{(2n+1)\times (2n+1)}(z)=\prod _{-n\le a,b \le n}(z-a+{\mathbf{i}}b). \end{aligned}$$

(26)

The Mignotte polynomial of degree d and bitsize $\tau$ is $M_{d,\tau }(z)=z^d - 2(2^{\frac{\tau }{2}-1}z-1)^2$.

We also consider dense polynomials of degree d with coefficients randomly chosen within $[-2^{\tau -1}, 2^{\tau -1}]$ (under the uniform distribution).

Results. In our test polynomials with several degrees/bit-sizes, we used Risolate, RisolateR and ANewDsc to solve the RRI problem. Our non-random examples have only simple roots and for those examples ANewDsc is called with option -S 1 to avoid testing input polynomial for being square-free.

Times are sequential times in seconds on a Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz machine with Linux. We report in Table 2:

• d, $\tau$ and $d_\mathbb R$, that is, the degree, the bit-size and the number of real roots, respectively,

• $t_1$ (resp. $t_2$), the running time of Risolate (resp. RisolateR),

• $n_1$ (resp. $n_2$), the number of $T^0$-tests in Risolate (resp. RisolateR),

• $n_1'$ (resp. $n_2'$), the number of $T^*$-tests in Risolate (resp. RisolateR),

• $t_3$, the time required to compute the annuli cover in RisolateR,

• $t_4$, the running time in second of ANewDsc.

For random polynomials, we display averages over 10 examples of those values. We also display $\sigma _1$, $\sigma _2$, and $\sigma _4$, the standard deviation of running time of Risolate, RisolateR and ANewDsc, respectively.

Table 2. Runs of Risolate, RisolateR and ANewDsc on our test polynomials

Compare columns $n_1,n_1'$ and $n_2,n_2'$ in Table 2: using the annuli cover both in exclusion tests and root counter reduces dramatically the number of Pellet’s tests performed in the subdivision process, and significantly decreases the running time (see column $t_2/t_1$). In the cases where the ratio $\tau /d$ is low RisolateR spent most of the time on solving the RRC problem (see column $t_3/t_2$). Finally, ANewDsc remains faster than RisolateR for polynomials having a few real roots or a low bit-size, whereas this trend seems to reverse when the ratios of the number of real roots and/or bit-size over the degree increase (see columns $t_2$ and $t_4$). Mignotte polynomials of even degree have four real roots among which two are separated by a distance way less than the relative size of $d^{-2}$, the relative size of annuli in the computed annuli cover. In such cases, the knowledge of root radii enables no significant improvement because subdivision solvers spend most of their running time on performing Newton’s iterations that converge to the cluster of two close roots, and then on separating the two roots.

4 Complex Root Clustering

In this section, by approximating the root distances from three centers, namely 0, 1 and ${\mathbf{i}}$ we improve practical performance of subdivision algorithms for complex root clustering.

Using three annuli covers $\mathcal {A}_0, \mathcal {A}_1$ and $\mathcal {A}_{{\mathbf{i}}}$ of the roots of $P$, one can compute a set $\mathcal {D}$ of $O(d^2)$ complex discs containing all the roots of $P$, and then skip expensive Pellet-based exclusion tests of the boxes that do not intersect the union of these discs.

In Subsect. 4.1 we describe an exclusion test using the set $\mathcal {D}$ of discs containing the roots of $P$, and in Subsect. 4.2 we present a procedure solving the CRC with near optimal bit complexity. In Subsect. 4.3 we show experimental results.

4.1 Annuli Cover and Exclusion Test

Let $\mathcal {D}$ be a set of $O(d^2)$ complex discs covering all the roots of $P$, i.e. any root of $P$ is in at least one disc in $\mathcal {D}$. A box B such that $B\cap \mathcal {D}=\emptyset$ cannot contain a root of $P$.

We define an exclusion test based on the above consideration, called $C_\mathbb C^0$-test and described in Algorithm 5. For a box B having a nonempty intersection with the real line, the number $n_{\ge 1}(\mathcal {A}_0,B)$ of annuli intersecting B and containing at least one real root in $B\cap \mathbb R$ is used to save some $T^0$-tests.

Proposition 12

Let $\mathcal {D}$ contain $O(d^2)$ discs covering the roots of $P$ and let $\mathcal {A}_0$ be an annuli cover of the roots of $P$ centered in 0. The cost of performing $C_\mathbb C^0(B, P,\mathcal {D}, \mathcal {A}_0)$ is bounded by the cost of performing $T^0(\Delta (B), P)$.

$C_\mathbb C^0(B, P,\mathcal {D}, \mathcal {A}_0)$ returns an integer k in $\{-1,0\}$. If $k=0$, then $P$ has no root in B. If $k=-1$, then $P$ has a root in 2B.

4.2 Annuli Cover and the CRC Problem

Consider the following procedure.

Stage 1: For $c=0,1,{\mathbf{i}}$, compute $\mathcal {A}_c$ by calling $\mathtt{SolveRRC}(P,c,d^{-2})$.

Stage 2: Use $\mathcal {A}_0$, $\mathcal {A}_1$ and $\mathcal {A}_{\mathbf{i}}$ to compute a set $\mathcal {D}$ of at most $2d^2$ discs covering all roots of $P$.

Stage 3: Apply the Complex Root Clustering Algorithm of Subsect. 1.2 but let it apply $C_\mathbb C^0(B, P,\mathcal {D},\mathcal {A}_0)$ instead of $T^0(\Delta (B), P)$ as the exclusion test for boxes B of the subdivision tree. In the verification step of Newton iterations, use the $T^*$-test of [2].

In Stage 1, for $c=0,1,{\mathbf{i}}$, $\mathcal {A}_c$ is obtained by computing the connected components of the concentric annnuli defined by the output of $\mathtt{SolveRRC}(P,c,d^{-2})$. According to Theorem 4, Stage 1 involves $\widetilde{O}( d^2(d+ \log \Vert P\Vert _\infty ) )$ bit operations.

In Stage 2, $\mathcal {D}$ is computed as follows: using double precision floating point arithmetic with correct rounding, first compute complex discs containing all possible intersections of an annulus in $\mathcal {A}_0$ with an annulus in $\mathcal {A}_1$, and obtain a set $\mathcal {D}$ of at most $2d^2$ complex discs containing all roots of $P$. Then, for each disc $\Delta$ in $\mathcal {D}$ check if $\Delta$ and its complex conjugate $\overline{\Delta }$ have a nonempty intersection with at least one annulus of $\mathcal {A}_{{\mathbf{i}}}$, and remove $\Delta$ from $\mathcal {D}$ if it does not. This step has cost in $O(d^3)$.

By virtue of Proposition 12, the cost of performing Stage 3 is bounded by the cost of performing the algorithm described in Subsect. 1.2. This procedure solves the CRC problem and supports near optimal complexity for the benchmark problem.

4.3 Experimental Results

The procedure of Subsect. 4.2 is implemented within Ccluster; below we call this implementation CclusterR and present experimental results that highlight practical improvement due to using our root radii algorithm in subdivision.

We used Ccluster and CclusterR with input value $\varepsilon =2^{-53}$ to find clusters of size at most $\varepsilon$. We also used MPSolve -3.2.1, with options -as -Ga -o16 -j1 to find approximations with 16 correct digits of the roots.

For our test polynomials (see 3.4) we report in Table 3:

• d and $\tau$ denoting the degree and the bit-size, respectively,

• $t_1$ (resp. $t_2$), the running time of Ccluster (resp. CclusterR),

• $n_1$ (resp. $n_2$), the number of $T^0$-tests in Ccluster (resp. CclusterR),

• $t_3$, the time for computing the three annuli covers in CclusterR, - $t_4$, the running time of MPSolve in seconds.

For random polynomials, we show averages over 10 examples of those values. We also show $\sigma _1$, $\sigma _2$, and $\sigma _4$, the standard deviations of the running times of Ccluster, CclusterR and MPSolve. For the real root isolator presented in Sect. 3, using root radii enables significant saving of Pellet-based exclusion tests in the subdivision process (compare columns $n_1$ and $n_2$) and yields a speed-up factor about 3 for our examples (see column $t_2/t_1$). This speed-up increases as the number of real roots increases (see, e.g., Wilkinson polynomials) because some exclusion tests for boxes B containing the real line are avoided when 2B contains at least one root which we can see from the number $n_{\ge 1}(\mathcal {A}_0,B)$ computed in the $C_\mathbb C^0$ test. The time spent for computing the three annuli covers remains low compared to the running time of CclusterR (see column $t_3/t_2$). MPSolve remains the user’s choice for approximating all complex roots.

Table 3. Runs of Ccluster, CclusterR and MPSolve on our test polynomials