Accelerated Subdivision for Clustering Roots of Polynomials Given by Evaluation Oracles

Abstract

In our quest for the design, the analysis and the implementation of a subdivision algorithm for finding the complex roots of univariate polynomials given by oracles for their evaluation, we present sub-algorithms allowing substantial acceleration of subdivision for complex roots clustering for such polynomials. We rely on approximation of the power sums of the roots in a fixed complex disc by Cauchy sums, each computed in a small number of evaluations of an input polynomial and its derivative, that is, in a polylogarithmic number in the degree. We describe root exclusion, root counting, root radius approximation and a procedure for contracting a disc towards the cluster of root it contains, called $\varepsilon$-compression. To demonstrate the efficiency of our algorithms, we combine them in a prototype root clustering algorithm. For computing clusters of roots of polynomials that can be evaluated fast, our implementation competes advantageously with user’s choice for root finding, MPsolve.

Victor’s research has been supported by NSF Grant CCF 1563942 and PSC CUNY Award 63677 00 51.

1 Introduction

We consider the

Here and hereafter root(s) stands for root(s) of $p$ and are counted with multiplicities, $3\varDelta ^j$ for the factor 3 concentric dilation of $\varDelta ^j$, and $p$ is a Black box polynomial: its coefficients are not known, but we are given evaluation oracles, that is, procedures for the evaluation of $p$, its derivative $p'$ and hence the ratio $p'/p$ at a point $c\in \mathbb C$ with a fixed precision. Such a black box polynomial can come from an experimental process or can be defined by a procedure, for example Mandelbrot’s polynomials, defined inductively as

$$ \mathtt{Man}_{1}(z) = z,~~ \mathtt{Man}_{k}(z) = z\,\mathtt{Man}_{k-1}(z)^2 + 1. $$

$\mathtt{Man}_{k}(z)$ has degree $d=2^{k}-1$ and $d$ non-zero coefficients but can be evaluated fast, i.e., in O(k) arithmetic operations. Any polynomial given by its coefficients can be handled as a black box polynomial, and the evaluation subroutines for $p, p'$ and $p'/p$ are fast if $p$ is sparse or Mandelbrot-like. One can solve root-finding problems and in particular the $\varepsilon$-CRC problem for black box polynomials by first retrieving the coefficients by means of evaluation-interpolation, e.g., with FFT and inverse FFT, and then by applying the algorithms of [2, 4, 11, 13, 19]. Evaluation-interpolation, however, decompresses the representation of a polynomial, which can blow up its input length, in particular, can destroy sparsity. We do not require knowledge of the coefficients of an input polynomial, but instead use evaluation oracles.

Functional root-finding iterations such as Newton’s, Weierstrass’s (also known as Durand-Kerner’s) and Ehrlich’s iterations – implemented in MPsolve  [4] – can be applied to approximate the roots of black box polynomials. Applying such iterations, however, requires initial points, which the known algorithms and in particular MPsolve obtain by computing root radii, and for that it needs the coefficients of the input polynomial.

Subdivision Algorithms. Let ${\mathbf{i}}$ stand for $\sqrt{-1}$, $c\in \mathbb C$, $c=a+{\mathbf{i}}b$ and $r,w\in \mathbb R$, r and w positive. We call box a square complex interval of the form $B(c,w):=[a-\frac{w}{2},a+\frac{w}{2}]+{\mathbf{i}}[b-\frac{w}{2},b+\frac{w}{2}]$ and disc $D(c, r)$ the set $\{ x\in \mathbb C~|~ |x-c|\le r\}$. The containing disc $D(B(c,w))$ of a box B(c, w) is $D(c,(3/4)w)$. For a $\delta >0$ and a box or a disc S, $\delta S$ denotes factor $\delta$ concentric dilation of S.

We consider algorithms based on iterative subdivision of an initial box $B_0$ (see [2, 3, 12]) and adopt the framework of [2, 3] which relies on two basic subroutines: an Exclusion Test (ET) – deciding that a small inflation of a disc contains no root – and a Root Counter (RC) – counting the number of roots in a small inflation of a disc. A box B of the subdivision tree is tested for root exclusion or inclusion by applying the ET and RC to $D(B)$, which can fail and return $-1$ when $D(B)$ has some roots near its boundary circle. In [2], ET and RC are based on the Pellet’s theorem, requiring the knowlege of the coefficients of $p$ and shifting the center of considered disc into the origin (Taylor’s shifts); then Dandelin-Lobachevsky-Gräffe iterations, aka root-squaring iterations, enable the following properties for boxes B and discs $\varDelta$:

(p1) if 2B contains no root, ET applied to $D(B)$ returns 0,

(p2) if $\varDelta$ and $4\varDelta$ contain m roots, RC applied to $2\varDelta$ returns m.

(p1) and (p2) bound the depth of the subdivision tree. To achieve quadratic convergence to clusters of roots, [2] uses a complex version of the Quadratic Interval Refinement iterations of J. Abbott [1], aka QIR Abbott iterations, described in details in Algorithm 7 of [3] and, like [12], based on extension of Newton’s iterations to multiple roots due to Schröder. [8] presents an implementation of [2] in the C library Ccluster¹, which slightly outperforms MPsolve for initial boxes containing only few roots.

In [6] we applied an ET based on Cauchy sums approximation. It satisfies (p1) and instead of coefficients of $p$ involves $O(\log ^2d)$ evaluations of $p'/p$ with precision O(d) for a disc with radius in O(1); although the output of this ET is only certified if no roots lie on or near the boundary of the input discs, in our extensive experiments it was correct when we dropped this condition.

1.1 Our Contributions

The ultimate goal of our work is to design an algorithm for solving the $\varepsilon$-CRC problem for black box polynomials which would run faster in practice than the known solvers, have low and possibly near optimal Boolean complexity (aka bit complexity). We do not achieve this yet in this paper but rather account for the advances along this path by presenting several sub-routines for root clustering. We implemented and assembled them in an experimental $\varepsilon$-CRC algorithm which outperforms the user’s choice software for complex root finding, MPsolve, for input polynomials that can be evaluated fast.

Cauchy ET and RC. We describe and analyze a new RC based on Cauchy sum computations and satisfying property (p2) which only require the knowledge of evaluation oracles. For input disc of radius in O(1), it requires evaluation of $p'/p$ at $O(\log ^2 d)$ points with precision O(d) and is based on our ET presented in [6]; the support for its correctness is only heuristic.

Disc Compression. For a set S, let us write $Z\left( S,p\right)$ for the set of roots in S and $\#\left( S,p\right)$ for the cardinality of $Z\left( S,p\right)$; two discs $\varDelta$ and $\varDelta '$ are said equivalent if $Z\left( \varDelta ,p\right) =Z\left( \varDelta ',p\right)$. We introduce a new sub-problem of $\varepsilon$-CRC:

The $\varepsilon$-CRD problem can be solved with subdivision and QIR Abbott iteration, but this may require, for an initial disk of radius r, up to $O(\log (r/\max (\varepsilon ',\varepsilon )))$ calls to the ET in the subdivision if the radius of convergence of the cluster in $\varDelta$ for Schröder’s iteration is in $O(\varepsilon ')$.

Table 1. Runs of CauchyQIR, CauchyComp and MPsolve on Mignotte and Mandelbrot polynomials

We present and analyze an algorithm solving the $\varepsilon$-CRD problem for $\gamma =1/8$ based on Cauchy sums approximation and on an algorithm solving the following root radius problem: for a given $c\in \mathbb C$, a given non-negative integer $m\le d$ and a $\nu >1$, find r such that $r_{m}(c,p)\le r \le \nu r_{m}(c,p)$ where $r_{m}(c,p)$ is the smallest radius of a disc centered in c and containing exactly m roots of $p$. Our compression algorithm requires only $O(\log \log (r/\varepsilon ))$ calls to our RC, but a number of evaluations and arithmetic operations increasing linearly with $\log (1/\varepsilon )$.

Experimental Results. We implemented our algorithms² within Ccluster and assembled them in two algorithms named CauchyQIR and CauchyComp for solving the $\varepsilon$-CRC problem for black box polynomials. Both implement the subdivision process of [2] with our heuristically correct ET and RC. CauchyQIR uses QIR Abbott iterations of [3] (with Pellet’s test replaced by our RC), while CauchyComp uses our compression algorithm instead of QIR Abbott iterations.

We compare runs of CauchyQIR and CauchyComp to emphasize the practical improvements allowed by using compression in subdivision algorithms for root finding. We also compare running times of CauchyComp and MPsolve to demonstrate that subdivision root finding can outperform solvers based on functional iterations for polynomials that can be evaluated fast. MPsolve does not cluster roots of a polynomial, but approximate each root up to a given error $\varepsilon$. Below we used the latest version³ of MPsolve and call it with: mpsolve -as -Ga -j1 -oN where N stands for $\max (1,\lceil \log _{10}(1/\varepsilon )\rceil )$.

All the timings given below have to be understood as sequential running times on a Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz machine with Linux. We highlight with boldface the best running time for each example. We present in Table 1 results obtained for Mandelbrot and Mignotte polynomials of increasing degree $d$ for decreasing error $\varepsilon$. The Mignotte polynomial of degree $d$ and parameter a is defined as

$$\begin{aligned} \mathtt{Mig}_{d,a}(z)=z^d - 2(2^{\frac{a}{2}-1}z-1)^2. \end{aligned}$$

In Table 1, we account for the running time t for the three above-mentionned solvers. For CauchyQIR (resp. CauchyComp), we also give the number n of exclusion tests in the subdivision process, and the time $t_N$ (resp. $t_C$) spent in QIR Abbott iterations (resp. compression). Mignotte polynomials have two roots with mutual distance close to the theoretical separation bound; with the $\varepsilon$ used in Table 1, those roots are not separated.

1.2 Related Work

The subdivision root-finders of Weyl 1924, Henrici 1974, Renegar 1987, [3, 12], rely on ET, RC and root radii sub-algorithms and heavily use the coefficients of $p$. Design and analysis of subdivision root-finders for a black box $p$ have been continuing since 2018 in [16] (now over 150 pages), relying on the novel idea and techniques of compression of a disc and on novel ET, RC and root radii sub-algorithms, and partly presented in [5, 6, 10, 14, 15], and this paper. A basic tool of Cauchy sum computation was used in [20] for polynomial deflation, but in a large body of our results only Thm. 5 is from [20]; we deduced it in [5, 16] from a new more general theorem of independent interest. Alternative derivation and analysis of subdivision in [16] (yielding a little stronger results but presently not included) relies on Schröder’s iterations, extended from [12]. The algorithms are analyzed in [10, 14,15,16], under the model for black box polynomial root-finding of [9]. [5, 6] complement this study with some estimates for computational precision and Boolean complexity. We plan to complete them using much more space (cf. 46 pages in each of [20] and [3]).⁴ Meanwhile we borrowed from [3] Pellet’s RC (involving coefficients), Abbott’s QIR and the general subdivision algorithm with connected components of boxes extended from [12, 18]. With our novel sub-algorithms, however, we significantly outperform MPsolve for polynomials that can be evaluated fast; all previous subdivision root-finders have never come close to such level. MPsolve relies on Ehrlich’s (aka Aberth’s) iterations, whose Boolean complexity is proved to be unbounded because iterations diverge for worst case inputs [17], but divergence never occurs in decades of extensive application of these iterations.

1.3 Structure of the Paper

In Sect. 2, we describe power sums and their approximation with Cauchy sums. In Sect. 3, we present and analyze our Cauchy ET and RC. Section 4 is devoted to root radii algorithms and Sect. 5 to the presentation of our algorithm solving the $\varepsilon$-CRD problem. We describe the experimental solvers CauchyQIR and CauchyComp in Sect. 6, numeric results in Sect. 7 and conclude in Sect. 8. We introduce additional definitions and properties in the rest of this section.

1.4 Definitions and Two Evaluations Bounds

Troughout this paper, $\log$ is the binary logarithm and for a positive real number a, let $\text {l}\overline{\text {og}}a=\max (1,\log a)$.

Annuli, Intervals. For $c\in \mathbb C$ and positives $r\le r'\in \mathbb R$, the annulus $A\left( c,r,r'\right)$ is the set $\{ z\in \mathbb C~|~ r'\le |z-c|\le r' \}$.

Let be the set $\{ [a-\frac{w}{2}, a+\frac{w}{2}] ~|~ a,w\in \mathbb R, w\ge 0 \}$ of real intervals. For  the center , the width and the radius  of are respectively a, w and w/2.

Let be the set of complex intervals. If , then (resp. ) is (resp ). The center  of is .

Isolation and Rigidity of a Disc are defined as follows [12, 16].

Definition 1

(Isolation) Let $\theta >1$. The disc $\varDelta =D(c,r)$ has isolation $\theta$ for a polynomial $p$ or equivalently is at least $\theta$-isolated if $Z\left( \frac{1}{\theta }\varDelta ,p\right) =Z\left( \theta \varDelta ,p\right)$, that is, $Z\left( A\left( c,r/\theta ,r\theta \right) ,p\right) =\emptyset$.

Definition 2

(Rigidity) For a disc $\varDelta =D(c,r)$, define

$$ \gamma (\varDelta )=\max _{\alpha , \alpha '\in Z\left( \varDelta ,p\right) } \frac{|\alpha - \alpha '|}{2r} $$

and remark that $\gamma (\varDelta )\le 1$. We say that $\varDelta$ has rigidity $\gamma$ or equivalently is at least $\gamma$-rigid if $\gamma (\varDelta )\ge \gamma$.

Oracle Numbers and Oracle Polynomials. Our algorithms deal with numbers that can be approximated arbitrarily closely by a Turing machine. We call such approximation automata oracle numbers and formalize them through interval arithmetic.

For $a\in \mathbb C$ we call oracle for a a function such that $a\in {\mathcal {O}}_{a}\left( {L}\right)$ and $\text {r}\left( {\mathcal {O}}_{a}\left( {L}\right) \right) \le 2^{-L}$ for any $L\in \mathbb N$. In particular, one has $| \text {c}\left( {\mathcal {O}}_{a}\left( {L}\right) \right) - a |\le 2^{-L}$. Let ${\mathcal {O}}_{\mathbb C}$ be the set of oracle numbers which can be computed with a Turing machine. For a polynomial $p\in \mathbb C[z]$, we call evaluation oracle for $p$ a function , such that if ${\mathcal {O}}_{a}$ is an oracle for a and $L\in \mathbb N$, then $p(a)\in {\mathcal {I}}_{p}\left( {{\mathcal {O}}_{a}},{L}\right)$ and $\text {r}\left( {\mathcal {I}}_{p}\left( {{\mathcal {O}}_{a}},{L}\right) \right) \le 2^{-L}$. In particular, one has $| \text {c}\left( {\mathcal {I}}_{p}\left( {{\mathcal {O}}_{a}},{L}\right) \right) - p(a) |\le 2^{-L}$.

Consider evaluation oracles ${\mathcal {I}}_{p}$ and ${\mathcal {I}}_{p'}$ for $p$ and $p'$. If $p$ is given by $d'\le d+1$ oracles for its coefficients, one can easily construct ${\mathcal {I}}_{p}$ and ${\mathcal {I}}_{p'}$ by using, for instance, Horner’s rule. However for procedural polynomials (e.g. Mandelbrot), fast evaluation oracles ${\mathcal {I}}_{p}$ and ${\mathcal {I}}_{p'}$ are built from procedural definitions.

To simplify notations, we let ${\mathcal {I}}_{p}\left( {a},{L}\right)$ stand for ${\mathcal {I}}_{p}\left( {{\mathcal {O}}_{a}},{L}\right)$. In the rest of the paper, ${\mathcal {P}}$ (resp. ${\mathcal {P}}'$) is an evaluation oracle for $p$ (resp. $p'$); ${\mathcal {P}}\left( {a},{L}\right)$ (resp. ${\mathcal {P}}'\left( {a},{L}\right)$) will stand for ${\mathcal {I}}_{p}\left( {{\mathcal {O}}_{a}},{L}\right)$ (resp. ${\mathcal {I}}_{p'}\left( {{\mathcal {O}}_{a}},{L}\right)$).

Two Evaluation Bounds. The lemma below provides estimates for values of $|p|$ and $|p'/p|$ on the boundary of isolated discs. See [7, Appendix A.1] for a proof.

Lemma 3

Let $D(c,r)$ be at least $\theta$-isolated, $z\in \mathbb C$, $|z|=1$ and g be a positive integer. Let $\text {lcf}\left( p\right)$ be the leading coefficient of $p$. Then

$$\begin{aligned} |p(c+rz^g)| \ge |\text {lcf}\left( p\right) |\frac{r^d(\theta -1)^d}{\theta ^d} ~~ \text { and }~~ \left| \frac{p'(c+rz^g)}{p(c+rz^g)}\right| \le \frac{d\theta }{r(\theta -1)}. \end{aligned}$$

2 Power Sums and Cauchy Sums

Definition 4

(Power sums of the roots in a disc) The h-th power sum of (the roots of) $p$ in the disc $D(c,r)$ is the complex number

$$\begin{aligned} s_{h}\left( {p},{c},{r}\right) =\sum \limits _{\alpha \in Z\left( \varDelta ,p\right) } \#\left( \alpha ,p\right) \alpha ^h, \end{aligned}$$

(1)

where $\#\left( \alpha ,p\right)$ stands for the multiplicity of $\alpha$ as a root of $p$.

The power sums $s_{h}\left( {p},{c},{r}\right)$ are equal to Cauchy’s integrals over the boundary circle $\partial D(c,r)$; by following [20] they can be approximated by Cauchy sums obtained by means of the discretization of the integrals: let $q\ge 1$ be an integer and $\zeta$ be a primitive q-th root of unity. When $p(c+r\zeta ^g)\ne 0$ for $g=0,\ldots ,q-1$, and in particular when $D(c,r)$ is at least $\theta$-isolated with $\theta >1$, define the Cauchy sum $\widetilde{s_{h}}^{q}\left( {p},{c},{r}\right)$ as

$$\begin{aligned} \widetilde{s_{h}}^{q}\left( {p},{c},{r}\right) =\frac{r}{q}\sum \limits _{g=0}^{q-1} \zeta ^{g(h+1)} \frac{p'(c+r\zeta ^g)}{p(c+r\zeta ^g)}. \end{aligned}$$

(2)

For conciseness of notations, we write $s_{h}$ for $s_{h}\left( {p},{0},{1}\right)$ and $\widetilde{s_{h}}^{q}$ for $\widetilde{s_{h}}^{q}\left( {p},{0},{1}\right)$. The following theorem, proved in [6, 20], allows us to approximate power sums by Cauchy sums in $D(0,1)$.

Theorem 5

For $\theta >1$ and integers h, q s.t. $0\le h < q$ let the unit disc $D(0,1)$ be at least $\theta$-isolated and contain m roots of $p$. Then

$$\begin{aligned} |\widetilde{s_{h}}^{q}-s_{h}| \le \dfrac{m\theta ^{-h}+ (d-m)\theta ^{h}}{\theta ^{q}-1}. \end{aligned}$$

(3)

$$\begin{aligned} \text {Fix }e>0\text {. If } q\ge \lceil \log _{\theta }(\frac{d}{e}) \rceil + h +1 \text { then }|\widetilde{s_{h}}^{q}-s_{h}| \le e. \end{aligned}$$

(4)

Remark that $s_{0}\left( {p},{c},{r}\right)$ is the number of roots of $p$ in $D(c,r)$ and $s_{1}\left( {p},{c},{r}\right) /m$ is their center of gravity when $m=\#\left( D(c,r),p\right)$.

Next we extend Theorm 5 to the approximation of 0-th and 1-st power sums by Cauchy sums in any disc, and define and analyze our basic algorithm for the computation of these power sums.

2.1 Approximation of the Power Sums

Let $\varDelta =D(c,r)$ and define $p_\varDelta (z)$ as $p(c+rz)$ so that $\alpha$ is a root of $p_\varDelta$ in $D(0,1)$ if and only if $c+r\alpha$ is a root of $p$ in $\varDelta$. Following Newton’s identities, one has:

$$\begin{aligned} s_{0}\left( {p},{c},{r}\right)&= s_{0}\left( {p_\varDelta },{0},{1}\right) ,\end{aligned}$$

(5)

$$\begin{aligned} s_{1}\left( {p},{c},{r}\right)&= cs_{0}\left( {p_\varDelta },{0},{1}\right) + rs_{1}\left( {p_\varDelta },{0},{1}\right) . \end{aligned}$$

(6)

Next since $p_{\varDelta }'(z)=rp'(c+rz)$, one has

$$\widetilde{s_{h}}^{q}\left( {p},{c},{r}\right) = \frac{1}{q}\sum \limits _{g=0}^{q-1} \zeta ^{g(h+1)} \frac{p_{\varDelta }'(\zeta ^g)}{p_{\varDelta }(\zeta ^g)} =\widetilde{s_{h}}^{q}\left( {p_{\varDelta }},{0},{1}\right) $$

and can easily prove:

Corollary 6

(of theorm 5) Let $\varDelta =D(c,r)$ be at least $\theta$-isolated. Let $q>1$, $s_0^* = \widetilde{s_{0}}^{q}\left( {p},{c},{r}\right)$ and $s_1^* = \widetilde{s_{1}}^{q}\left( {p},{c},{r}\right)$. Let $e>0$. One has

$$\begin{aligned} |s_0^*-s_{0}\left( {p},{c},{r}\right) | \le \dfrac{d}{\theta ^{q}-1}. \end{aligned}$$

(7)

$$\begin{aligned} \text {If } q\ge \lceil \log _{\theta }(1 + \frac{d}{e}) \rceil \text { then }|s_0^*-s_{0}\left( {p},{c},{r}\right) | \le e. \end{aligned}$$

(8)

Let $\varDelta$ contain m roots.

$$\begin{aligned} |mc+rs_1^*-s_{1}\left( {p},{c},{r}\right) | \le \dfrac{rd\theta }{\theta ^{q}-1}. \end{aligned}$$

(9)

$$\begin{aligned} \text {If } q\ge \lceil \log _{\theta }(1+\frac{r\theta d}{e}) \rceil \text { then }|mc+rs_1^*-s_{1}\left( {p},{c},{r}\right) | \le e. \end{aligned}$$

(10)

2.2 Computation of Cauchy Sums

Next we suppose that $D(c,r)$ and q are such that $p(c+r\zeta ^g)\ne 0$ $\forall 0\le g < q$, so that $\widetilde{s_{h}}^{q}\left( {p},{c},{r}\right)$ is well defined. We approximate Cauchy sums with evaluation oracles ${\mathcal {P}}$, ${\mathcal {P}}'$ by choosing a sufficiently large L and computing the complex interval:

(11)

is well defined for $L > \max _{0\le g < q} \left( -\log _2 ( p(c+r\zeta ^g) )\right)$ and contains $\widetilde{s_{h}}^{q}\left( {p},{c},{r}\right)$. The following result specifies L for which we obtain that for an $e>0$. See [7, Appendix A.2] for a proof.

Lemma 7

For strictly positive integer d, reals r and e and $\theta >1$, let

$$\begin{aligned} L\left( d,r,e,\theta \right)&:= \max \left( (d+1) \log { \frac{\theta }{er(\theta -1)} } + \log (26rd),1 \right) \\&\in O\left( d\left( \text {l}\overline{\text {og}}\frac{1}{re} + \log \frac{\theta }{\theta -1} \right) \right) . \end{aligned}$$

If $L\ge L\left( d,r,e, \theta \right)$ then .

In the sequel let $L\left( d,r\right)$ stand for $L\left( d,r,1/4,2\right)$.

2.3 Approximating the Power Sums $s_{0},s_{1}, \ldots , s_{h}$

Our Algorithm 1 computes, for a given integer h, approximations to power sums $s_{0}, s_{1}, \ldots , s_{h}$ (of $p_\varDelta$ in $D(0,1)$) up to an error e, based on Eqs. (2) and (4).

Algorithm 1 satisfies the following proposition. See [7, Appendix A.3] for a proof.

Proposition 8

Algorithm 1 terminates for an $L\le L\left( d, r, e/4, \theta \right)$.

Let $\mathbf{ApproxShs}({\mathcal {P}}, {\mathcal {P}}', \varDelta , \theta , h, e)$ return . Let $\varDelta =~$ $D(c,r)$ and $p_{\varDelta }(z) = p(c+rz)$. If $\theta >1$, one has:

• (a) If $A(c,r/\theta , r\theta )$ contains no root of $p$, then $success = true$ and for all $i\in \{0,\ldots , h\}$, and contains $s_{i}\left( {p_\varDelta },{0},{1}\right)$.

• (b) If $e\le 1$ and $D(c,r\theta )$ contains no root of $p$ then $success = true$ and for all $i\in \{0,\ldots , h\}$, contains the unique integer 0.

• (c) If $e\le 1$ and $A(c,r/\theta , r\theta )$ contains no root of $p$, contains the unique integer $s_{0}\left( {p},{c},{r}\right) =\#\left( \varDelta ,p\right)$.

• (d) If $success = false$, then $A(c,r/\theta , r\theta )$ and $D(c,r\theta )$ contain (at least) a root of $p$.

• (e) If $success = true$ and $\exists i\in \{0,\ldots , h\}$, s.t. does not contain 0 then $A(c,r/\theta , r\theta )$ and $D(c,r\theta )$ contains (at least) a root of $p$.

3 Exclusion Test and Root Counters

In this section we define and analyse our base tools for disc exclusion and root counting. We recall in Subsect. 3.1 and Subsect. 3.2 the RC and the ET presented in [6]. In Subsect. 3.3, we propose a heuristic certification of root counting in which the assumed isolation for a disc $\varDelta$ is heuristically verified by applying sufficiently many ETs on the contour of $\varDelta$.

For $d\ge 1, r>0$ and $\theta >1$, define

$$\begin{aligned} C\left( d,r,e,\theta \right) := \log (L\left( d,r,e,\theta \right) )\log _\theta (d/e) \end{aligned}$$

(12)

and $C\left( d,r\right) = C\left( d,r,1/4,2\right)$.

3.1 Root Counting with Known Isolation

For a disc $\varDelta$ which is at least $\theta$-isolated for $\theta >1$, Algorithm 2 computes the number m of roots in $\varDelta$ as the unique integer in the interval of width $<1$ obtained by approximating 0-th cauchy sum of $p_\varDelta$ in the unit disc within error $<1/2$.

Proposition 9

Let $\varDelta =D(c,r)$. $\mathbf{CauchyRC1}({\mathcal {P}}, {\mathcal {P}}', \varDelta , \theta )$ requires evaluation of ${\mathcal {P}}$ and ${\mathcal {P}}'$ at $O(C\left( d,r,1,\theta \right) )$ points and $O(C\left( d,r,1,\theta \right) )$ arithmetic operations, all with precision less than $L\left( d, r,1/4, \theta \right)$. Let m be the output of the latter call.

• (a) If $A\left( c,r/\theta , r\theta \right)$ contains no roots of $p$ then $m=\#\left( \varDelta ,p\right)$.

• (b) If $m\ne 0$ then $p$ has a root in the disc $\theta \varDelta$.

Proposition 9 is a direct consequence of Proposition 8: in each execution of the while loop in $\mathbf{ApproxShs}({\mathcal {P}}, {\mathcal {P}}', \varDelta , \theta , 0, 1)$, ${\mathcal {P}}$ and ${\mathcal {P}}'$ are evaluated at $O(\log _{\theta }d/e)$ points and the while loop executes an $O(\log ( L\left( d, r, 1, \theta \right) ))$ number of times.

3.2 Cauchy Exclusion Test

We follow [6] and increase the chances for obtaining a correct result for the exclusion of a disc with unknown isolation by approximating the first three power sums of $p_\varDelta$ in $D(0,1)$ in Algorithm 3. One has:

Proposition 10

Let $\varDelta =D(c,r)$. $\mathbf{CauchyET}({\mathcal {P}}, {\mathcal {P}}', \varDelta )$ requires evaluation of ${\mathcal {P}}$ and ${\mathcal {P}}'$ at $O(C\left( d, r\right) )$ points and $O(C\left( d, r\right) )$ arithmetic operations, all with precision less than $L\left( d, r\right)$. Let m be the output of the latter call.

• (a) If $D(c, 4r/3)$ contains no roots of $p$ then $m=0$. Let B be a box so that 2B contains no root and suppose $\varDelta =D(B)$; then $m=0$.

• (b) If $m\ne 0$ then $p$ has a root in the disc $(4/3)\varDelta$.

3.3 Cauchy Root Counter

We begin with a lemma illustrated in Fig. 1. See [7, Appendix A.4] for a proof.

Lemma 11

Let $c\in \mathbb C$ and $\rho _-,\rho _+\in \mathbb R$. Define $\mu =\frac{\rho _+ + \rho _-}{2}$, $\rho =\frac{\rho _+ - \rho _-}{2}$, $w=\frac{\mu }{\rho }$, $v=\lceil 2\pi w \rceil$ and $c_j = c + \mu e^{j\frac{2\pi {\mathbf{i}}}{v}}$ for $j=0,\ldots ,v-1$. Then the re-union of the discs $D(c_j,(5/4)\rho )$ covers the annulus $A\left( c, \rho _-, \rho _+\right)$.

Fig. 1.

Illustration for Lemma 11. In bold line, the inner and outer circles of the annulus covered by the v discs $D(c_j,(5/4)\rho )$.

For a disc $D(c,r)$ and a given $a>1$, we follow Lemma 11 and cover the annulus $A\left( c, r/a, ra\right)$ with v discs of radius $r\frac{5(a-1/a)}{4*2}$ centered at v equally spaced points of the boundary circle of $D(c,r\frac{a+1/a}{2})$. Define

$$\begin{aligned} f_-(a,\theta ) = \frac{1}{2}(a(1-\frac{5}{4}\theta ) + \frac{1}{a}(1+\frac{5}{4}\theta )) \end{aligned}$$

(13)

and

$$\begin{aligned} f_+(a,\theta ) = \frac{1}{2}(a(1+\frac{5}{4}\theta ) + \frac{1}{a}(1-\frac{5}{4}\theta )), \end{aligned}$$

(14)

then the annulus $A\left( c, rf_-(a,\theta ), rf_+(a,\theta )\right)$ covers the $\theta$-inflation of those v discs.

Algorithm 4 counts the number of roots of $p$ in a disc and satisfies:

Proposition 12

The call $\mathbf{CauchyRC2}({\mathcal {P}}, {\mathcal {P}}', \varDelta , a)$ amounts to $\lceil 2\pi \frac{a^2+1}{a^2-1}\rceil$ calls to $\mathbf{CauchyET}$ and one call to $\mathbf{CauchyRC1}$.

Let $\varDelta =D(c,r)$ and A be the annulus $A\left( c,rf_-(a,\frac{4}{3}), rf_+(a,\frac{4}{3})\right)$. Let m be the output of the latter call.

• (a) If A contains no root then $m\ge 0$ and $\varDelta$ contains m roots.

• (b) If $m\ne 0$, then A contains a root.

We state the following corollary.

Corollary 13

(of Proposition 12) Let $\theta =4/3$ and $a=11/10$. Remark that

$$ f_-(a,\theta ) = \frac{93}{110} > 2^{-1/4} \text { and } f_+(a,\theta ) = \frac{64}{55}. $$

The call $\mathbf{CauchyRC2}({\mathcal {P}}, {\mathcal {P}}', \varDelta , a)$ amounts to $\lceil 2\pi \frac{a^2+1}{a^2-1}\rceil =67$ calls to CauchyET for discs of radius $\frac{21}{176}r\in O(r)$ and one call to $\mathbf{CauchyRC1}$ for $\varDelta$. This requires evaluation of ${\mathcal {P}}$ and ${\mathcal {P}}'$ at $O(C\left( d, r\right) )$ points, and $O(C\left( d, r\right) )$ arithmetic operations, all with precision less than $L\left( d, r\right)$.

4 Root Radii Algorithms

4.1 Approximation of the Largest Root Radius

For a monic $p$ of degree $d$ and bit-size $\tau =\log \Vert p\Vert _1$, we describe a naive approach to the approximation of the largest modulus $r_d$ of a root of $p$. Recall Cauchy’s bound for such a polynomial: $r_d\le 1+2^{\tau }$. The procedure below finds an r so that $r_d<r$ and either $r=1$ or $r/2 < r_d$ when $p$ is given by the evaluation oracles ${\mathcal {P}}, {\mathcal {P}}'$.

As a consequence of Proposition 12 each execution of the while loop terminates and the procedure terminates after no more than $O(\tau )$ execution of the while loop. It requires evaluation of ${\mathcal {P}}$ and ${\mathcal {P}}'$ at $O(\tau C\left( d, r\right) )$ points and $O(\tau C\left( d, r\right) )$ arithmetic operations all with precision less than $L\left( d, r\right)$. Its correctness is implied by correctness of the results of $\mathbf{CauchyRC2}$ which is in turn implied by correctness of the results of $\mathbf{CauchyET}$.

4.2 Approximation of the $(d+1-m)$-th Root Radius

For a $c\in \mathbb C$ and an integer $m\ge 1$, we call $(d+1-m)$-th root radius from c and write it $r_{m}(c,p)$ the smallest radius of a disc centered in c and containing exactly m roots of $p$.

Algorithm 5 approximates $r_{m}(c,p)$ within the relative error $\nu$. It is based on the RC $\mathbf{CauchyRC2}$ and reduces the width of an initial interval [l, u] containing $r_{m}(c,p)$ with a double exponential sieve.

The correctness of Algorithm 5 for given input parameters is implied by correctness of the results of $\mathbf{CauchyRC2}$ which is in turn implied by correctness of the results of $\mathbf{CauchyET}$. Algorithm 5 satisfies the proposition below. See [7, Appendix A.5] for a proof.

Proposition 14

The call $\mathbf{RootRadius}({\mathcal {P}}, {\mathcal {P}}', D(c,r), m, \nu , \varepsilon )$ terminates after $O(\log \log (r/\varepsilon ))$ iterations of the while loop. Let $\varDelta =D(c,r)$ and $r'$ be the output of the latter call.

• (a) If $\varDelta$ contains at least a root of $p$ then so does $D(c,2r')$.

• (b) If $\varDelta$ contains m roots of $p$ and $\mathbf{CauchyRC2}$ returns a correct result each time it is called in Algorithm 5, then either $r'=\varepsilon$ and $r_m(c,p)\le \varepsilon$, or $r_m(c,p)\le r' \le \nu r_m(c,p)$.

5 A Compression Algorithm

We begin with a geometric lemma illustrated in Fig. 2.

Lemma 15

Let $c\in \mathbb C$ and $r, \varepsilon , \theta \in \mathbb R$ satisfying $0<\varepsilon \le r/2$ and $\theta \ge 2$. Let $c'\in D(c, \frac{r+\varepsilon }{\theta })$ and $u=\max \left( \left| c-c'\right| + \frac{r}{\theta }, r\right)$. Then

$$ D\left( c,\frac{r}{\theta }\right) \subseteq D\left( c', u\right) \subseteq D\left( c,\frac{7}{4}r\right) \subset D(c,r\theta ). $$

Fig. 2.

Illustration for Lemma 15 with $\theta =2$ and $\varepsilon = r/4$. $c'$ is on the boundary circle of $D(c,(r+\varepsilon )/2)$, and $u:=\left| c-c'\right| + r/\theta$.

The following lemma is a direct consequence of Lemma 15 because $s_{1}\left( {p},{c},{r}\right) /m$ is the center of gravity of the roots of $p$ in $D(c,r)$.

Lemma 16

Let D(c, r) be at least $\theta \ge 2$-isolated and contain m roots. Let $s_1^*$ approximate $s_1(p, c, r)$ such that $|s_1^*-s_1(p,c,r)|\le \frac{m\varepsilon }{\theta }$ and $\varepsilon \le \frac{r}{2}$. Then for $c' = \frac{s_1^*}{m}$ and $u=\max \left( \left| c-c'\right| + \frac{r}{\theta }, r \right)$, the disc $D(c',u)$ contains the same roots of $p$ as D(c, r).

Algorithm 6 solves the $\varepsilon$-CRD problem for $\gamma =1/8$. It satisfies the proposition below. See [7, Appendix A.6] for a proof.

Proposition 17

The call $\mathbf{Compression}({\mathcal {P}}, {\mathcal {P}}', \varDelta , \varepsilon )$ where $\varDelta =D(c,r)$ requires evaluation of ${\mathcal {P}}$ and ${\mathcal {P}}'$ at $O \left( C\left( d, \varepsilon \right) \text {l}\overline{\text {og}}\text {l}\overline{\text {og}}\frac{r}{\varepsilon } \right)$ points and the same number of arithmetic operations, all with precision less than $L\left( d, \varepsilon /4\right)$. Let $m, D(c',r')$ be the output of the latter call.

• (a) If $\varDelta$ is at least 2-isolated and $Z\left( \varDelta ,p\right) \ne \emptyset$, and if the call to $\mathbf{RootRadius}$ returns a correct result, then $D(c',r')$ is equivalent to $\varDelta$, contains m roots of $p$ and satisfies: either $r'\le \varepsilon$, or $D(c',r')$ is at least 1/8-rigid.

• (b) If $m'>0$ then $D(c',2r')$ contains at least a root of $p$.

6 Two Cauchy Root Finders

In order to demonstrate the efficiency of the algorithms presented in this paper, we describe here two experimental subdivision algorithms, named $\texttt {CauchyQIR}$ and $\texttt {CauchyComp}$, solving the $\varepsilon$-CRC problem for oracle polynomials based on our Cauchy ET and RCs. Both algorithms can fail –in the case where $\mathbf{CauchyET}$ excludes a box of the subdivision tree containing a root – but account for such a failure. Both algorithm adapt the subdivision process described in [2]. $\texttt {CauchyQIR}$ uses QIR Abbott iterations to ensure fast convergence towards clusters of roots. $\texttt {CauchyComp}$ uses $\varepsilon$-compression presented in Sect. 5. In both solvers, the main subdivision loop is followed by a post-processing step to check that the output is a solution of the $\varepsilon$-CRC problem. The main subdivision loop does not involve coefficients of input polynomials but use evaluation oracles instead. However, we use coefficients obtained by evaluation-interpolation in the post-processing step in the case where some output discs contain more than one root. We observe no failure of our algorithms in all our experiments covered in Sect. 7.

6.1 Subdivision Loop

Let $B_0$ be a box containing all the roots of $p$. Such a box can be obtained by applying the process described in Subsect. 4.1.

Sub-Boxes, Component and Quadrisection. For a box $B(a+{\mathbf{i}}b,w)$, let $Children_1(B)$ be the set of the four boxes $\{ B( (a\pm w/4) + {\mathbf{i}}(b\pm w/4), w/2) \}$, and

$$ Children_n(B) :=\bigcup _{B'\in Children_{n-1}(B)} Children_1(B'). $$

A box B is a sub-box of $B_0$ if $B=B_0$ or if there exist an $n\ge 1$ s.t. $B\in Children_n(B_0)$. A component C is a set of connected sub-boxes of $B_0$ of equal widths. The component box B(C) of a component C is the smallest (square) box subject to $C\subseteq B(C)\subseteq B_0$ minimizing both ${\mathcal Re}(\text {c}\left( B(C)\right) )$ and ${\mathcal Im}(\text {c}\left( B(C)\right) )$. We write $D(C)$ for $D(B(C))$. If S is a set of components (resp. discs) and $\delta >0$, write $\delta S$ for the set $\{ \delta D(A) \text { (resp. } A) ~|~ A\in S\}$.

Definition 18

Let Q be a set of components or discs. We say that a component C (resp. a disk $\varDelta$) is $\gamma$-separated (or $\gamma$-sep.) from Q when $\gamma D(C)$ (resp. $\gamma \varDelta$) has empty intersection with all elements in Q.

Remark 19

Let Q be a set of components and $C\notin Q$ a component. If $Z\left( \mathbb C,p\right) =Z\left( \{C\}\cup Q,p\right)$ and C is 4-separated from Q then $2D(C)$ is at least 2-isolated.

Subdivision Process. We describe in Algorithm 7 a subdivision algorithm solving the $\varepsilon$-CRC problem. The components in the working queue Q are sorted by decreasing radii of their containing discs. It is parameterized by the flag compression indicating whether compression or QIR Abbott iterations have to be used. In QIR Abbott iterations of Algorithm 7 in [3], we replace the Graeffe Pellet test for counting roots in a disc $\varDelta$ by $\mathbf{CauchyRC2}({\mathcal {P}}, {\mathcal {P}}', \varDelta , 4/3)$. If a QIR Abbott iteration in step 12 fails for input $\varDelta , m$, it returns $\varDelta$. Steps 20–21 prevent C to artificially inflate when a compression or a QIR Abbott iteration step does not decrease $D(C)$. For a component C, Quadrisect(C) is the set of components obtained by grouping the set of boxes

$$ \bigcup _{B\in C} \left\{ B'\in Children_1(B) ~|~ \mathbf{CauchyET}({\mathcal {P}}, {\mathcal {P}}', D(B')) = -1 \right\} $$

into components.

The while loop in steps 4-22 terminates because all our algorithms terminate, and as a consequence of (a) in Proposition 9: any component will eventually be decreased until the radius of its containing disc reaches $\varepsilon /2$.

6.2 Output Verification

After the subdivision process described in steps 1–22 of Algorithm. 7, R is a set of pairs of the form $\{(\varDelta ^1,m^1),\ldots ,(\varDelta ^\ell ,m^\ell )\}$ satisfying, for any $1\le j\le \ell$:

• $\varDelta ^j$ is a disc of radii $\le \varepsilon$, $m^j$ is an integer $\ge 1$,

• $\varDelta ^j$ contains at least a root of $p$,

• for any $1\le j'\le \ell$ s.t. $j'\ne j$, $3\varDelta ^j\cap \varDelta ^{j'}=\emptyset$.

The second property follows from (b) of Proposition 10 and (b) of Proposition 17 when compression is used. Otherwise, remark that a disk $\varDelta$ in the output of QIR Abbott iteration in step 12 of Algorithm 7 verifies $\mathbf{CauchyRC2}({\mathcal {P}}, {\mathcal {P}}', \varDelta , 4/3)>0$ and apply (b) of Proposition 12. The third property follows from the if statement in step 15 of Algorithm 7. Decompose R as the disjoint union $R_1\cup R_{>1}$ where $R_1$ is the subset of pairs $(\varDelta ^i,m^i)$ of R where $m^i=1$ and $R_{>1}$ is the subset of pairs $(\varDelta ^i,m^i)$ of R where $m^i>1$, and make the following remark:

Remark 20

If $m^1+\ldots +m^\ell = d$ and for any $(\varDelta ^i,m^i)\in R_{>1}$, $\varDelta ^i$ contains exactly $m^i$ roots of $p$, then R is a correct output for the $\varepsilon$-CRC problem with input $p$ of degree $d$ and $\varepsilon$.

According to Remark 20, checking that R is a correct output for the $\varepsilon$-CRC problem for fixed input $p$ of degree $d$ and $\varepsilon$ amount to check that the $m^i$’s add up to $d$ and that for any $\varDelta ^i\in R_{>1}$, $\varDelta ^i$ contains exactly $m^i$ roots of $p$. For this last task, we use evaluation-interpolation to approximate the coefficients of $p$ and then apply the Graeffe-Pellet test of [2].

7 Experiments

We implemented Algorithm 7 in the C library Ccluster. Call CauchyComp (resp. CauchyQIR) the implementation of Algorithm 7 with $compression=true$ (resp. false). In the experiments we conducted so far, CauchyComp and CauchyQIR never failed.

Test Suite. We experimented CauchyComp, CauchyQIR and MPsolve on Mandelbrot and Mignotte polynomials as defined in Sect. 1 as well as Runnel and random sparse polynomials. Let $r=2$. The Runnel polynomial is defined inductively as

$$ \mathtt{Run}_{0}(z)=1,~~\mathtt{Run}_{1}(z)=z,~~ \mathtt{Run}_{k+1}(z) = \mathtt{Run}_{k}(z)^r + z\,\mathtt{Run}_{k-1}(z)^{r^2} $$

It has real coefficients, a multiple root (zero), and can be evaluated fast. We generate random sparse polynomials of degree $d$, bitsize $\tau$ and $\ell \ge 2$ non-zero terms as follows, where $p_i$ stands for the coefficient of the monomial of degree i in $p$: $p_0$ and $p_d$ are randomly chosen in $[-2^{\tau -1},2^{\tau -1}]$, then $\ell -2$ integers $i_1,\ldots ,i_{\ell -1}$ are randomly chosen in $[1,d-1]$ and $p_{i_1},\ldots ,p_{i_{\ell -1}}$ are randomly chosen in $[-2^{\tau -1},2^{\tau -1}]$. The other coefficients are set to 0.

Results. We report in Table 1 results of those experiments for Mandelbrot and Mignotte polynomials with increasing degrees and increasing values of $\log _{10}(\varepsilon ^{-1})$. We account for the running time t for the three above-mentionned solvers. For CauchyQIR (resp. CauchyComp), we also give the number n of exclusion tests in the subdivision process, and the time $t_N$ (resp. $t_C$) spent in QIR Abbott iterations (resp. compression).

Our compression algorithm allows smaller running times for low values of $\log _{10}(\varepsilon ^{-1})$ because it compresses a component C on the cluster it contains as of $2D(C)$ is 2-isolated, whereas QIR Abbott iterations require the radius $\varDelta$ to be near the radius of convergence of the cluster for Schröder’s iterations.

We report in Table 2 the results of runs of CauchyComp and MPsolve for polynomials of our test suite of increasing degree, for $\log _{10}(\varepsilon ^{-1})=16$. For random sparse polynomials, we report averages over 10 examples. The column $t_V$ accounts for the time spent in the verification of the output of CauchyComp (see Subsect. 6.2); it is 0 when all the pairs $(\varDelta ^j,m^j)$ in the output verify $m^j=1$. It is $>0$ when there is at least a pair with $m^j>1$.

The maximum precision L required in all our tests was 106, which makes us believe that our analysis in Proposition 8 is very pessimistic. Our experimental solver CauchyComp is faster than MPsolve for polynomials that can be evaluated fast.

Table 2. Runs of CauchyComp and MPsolve on polynomials of our test suite for $\log _{10}(\varepsilon ^{-1})=16$

8 Conclusion

We presented, analyzed and verified practical efficiency of two basic subroutines for solving the complex root clustering problem for black box polynomials. One is a root counter, the other one is a compression algorithm. Both algorithms are well-known tools used in subdivision procedures for root finding.

We propose our compression algorithm not as a replacement of QIR Abbott iterations, but rather as a complementary tool: in future work, we plan to use compression to obtain a disc where Schröder’s/QIR Abbott iterations would converge fast. The subroutines presented in this paper laid down the path toward a Cauchy Root Finder, that is, an algorithm solving the $\varepsilon$-CRC problem for black box polynomials.