Rémi Imbach
email: remi.imbach@nyu.edu

Marc Pouget
email: marc.pouget@inria.fr

Chee Yap
email: yap@cs.nyu.edu

Clustering Complex Zeros of Triangular System of Polynomials

Keywords: complex root finding, triangular polynomial system, nearoptimal root isolation, certified algorithm, complex root isolation, oracle multivariable polynomial, subdivision algorithm, Pellet'

) for clustering the complex roots of a univariate polynomial where the coefficients are represented by number oracles. Our algorithm is numeric, produces guaranteed results and is based on subdivision. We implemented it and compared it with state of the art solvers on various triangular systems, including systems with clusters of solutions or multiple solutions.

Introduction

This report considers the fundamental problem of finding the complex solutions of a system f (z) = 0 of n polynomial equations in n complex variables z = (z 1 , . . . , z n ). We will call triangular a system f = (f 1 , . . . , f n ) : C n → C n where f i ∈ C[z 1 , . . . , z i ] for 1 ≤ i ≤ n. Throughout this paper, we use boldface symbols to denote vectors and tuples; for instance 0 stands for (0, . . . , 0).

We are interested in finding clusters of solutions of triangular systems and in counting the total multiplicity of solutions in clusters. Solving triangular systems is a fundamental task in polynomial equations solving, since many algebraic approaches (Gröbner basis, CAD, resultants,. . . ) generally reduce the original system to triangular systems. The problem of isolating the complex solutions of a polynomial system in an initial region-of-interest (ROI) is defined as follows: let Zero(B, f ) denote the set of solutions of f in B, regarded3 as a multiset.

Local Isolation Problem (LIP): Given: a polynomial map f :

C n → C n , a polybox B ⊂ C n , > 0 Output: a set {∆ 1 , . . . , ∆ l } of pairwise disjoint polydiscs of radius ≤ where -Zero(B, f ) = l j=1 Zero(∆ j , f ). -each Zero(∆ j , f ) is a singleton.
This is "local" because we restrict attention to roots in a ROI B. There are two issues with (LIP) as formulated above: deciding if Zero(∆ j , f ) is a singleton, and deciding if such a singleton lies in B, are two "zero problems" that require exact computation. Generally, this can only be decided if f is algebraic. Even in the algebraic case, this may be very expensive. In [START_REF] Yap | Analytic root clustering: A complete algorithm using soft zero tests[END_REF][START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF] these two issues are sidestepped for the univariate case by defining the local clustering problem which is described next in a multivariate setting.

Before proceeding, we fix some notations. A polydisc ∆ is a vector of complex discs. The center (resp. radius r(∆)) of ∆ is the vector of the centers (resp. radii) of its components. If δ is any positive real number, we denote by δ∆ the polydisc that has the same center than ∆ and radius δr(∆). We also say r

(∆) ≤ δ if each component of r(∆) is ≤ δ. A (square complex) box B is a complex interval [ 1 , u 1 ] + i([ 2 , u 2 ]) where u 2 -2 = u 1 -1 and i := √ -1; the width w(B) of B is u 1 -1 and the center of B is u 1 + w(B) 2 + i(u 2 + w(B)
2 ). A polybox B ∈ C n is a vector boxes. The center (resp. width w(B)) of B is the vector of the centers (resp. widths) of its components. If δ is any positive real number, we denote by δB the polybox that has the same center than B and width δw(B).

We introduce three notions to define the local solution clustering problem. Let a ∈ C n be a solution of f (z) = 0. The multiplicity of a in f , also called the intersection multiplicity of a in f is classically defined by localization of rings as in [6, Def. 1, p. 61], we denote it by #(a, f ). An equivalent definition uses dual spaces, see [START_REF] Dayton | Computing the multiplicity structure in solving polynomial systems[END_REF]Def. 1,p. 117]. For any set S ⊆ C n , we denote by Zero(S, f ) the multiset of zeros of f in S, and #(S, f ) the total multiplicity of Zero(S, f ). If S is a polydisc so that Zero(S, f )is non-empty, we call Zero(S, f ) a cluster and S an isolator of the cluster. If in addition, we have that Zero(S, f ) = Zero(3 • S, f ), we call Zero(S, f ) a natural cluster and call S a natural isolator. In the context of numerical algorithm, the notion of cluster of solutions is more meaningful than that of solution with multiplicity since the perturbation of a multiple solution generates a cluster. We thus "soften" the problem of isolating the solutions of a triangular system of polynomial equations while counting their multiplicities by translating it into the local solution clustering problem defined as follows:

Local Clustering Problem (LCP): Given: a polynomial map f : C n → C n , a polybox B ⊂ C n , > 0 Output: a set of pairs {(∆ 1 , m 1 ), . . . , (∆ l , m l )} where:

-the ∆ j s are pairwise disjoint polydiscs of radius ≤ , -each

m j = #(∆ j , f ) = #(3∆ j , f ) -Zero(B, f ) ⊆ l j=1 Zero(∆ j , f ) ⊆ Zero(2B, f ).
In this (LCP) reformulation of (LIP), we have removed the two "zero problems" noted above: we output clusters to avoid the first one, and we allow the output to contain zeroes outside the ROI B to avoid the second one. We choose 2B for simplicity; it is easy to replace the factor of 2 by 1 + δ for any desired δ > 0.

Our contributions

We propose an algorithm for solving the (LCP), i.e. computing natural clusters, for a triangular system f (z) = 0 with a zero-dimensional solution set. To this end, we propose a formula to count the sum of multiplicities of solutions in a cluster. Our formula is derived from a result of [START_REF] Zhang | Real solution isolation with multiplicity of zerodimensional triangular systems[END_REF] that links the intersection multiplicity of a solution of a triangular system to multiplicities in fibers. We define towers of clusters to encode clusters of solutions of a triangular system in stacks (or towers) of clusters of roots of univariate polynomials. Our algorithm leverages from the triangular form of f : it computes first clusters of solutions of f 1 = • • • = f n-1 = 0, then clusters of roots of f n on fibers over clusters previously found. The components of those fibers are clusters of roots of univariate polynomials that are advantageously represented by oracles; oracle means here a procedure providing approximations at any precision.

We propose a bound on the loss of accuracy induced by the specialization of f n on a fiber approximated at a given precision; the coefficients of f n specialized in oracle fibers are thus also known by oracles.

To compute clusters of roots of a univariate polynomial given as an oracle, we rely on the recent algorithm described in [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF], based on a predicate introduced in [START_REF] Becker | A near-optimal subdivision algorithm for complex root isolation based on Pellet test and Newton iteration[END_REF] that combines Pellet's theorem and Graeffe iterations to determine the number of roots counted with multiplicities in a complex disc; this predicate is called soft because it only requires the polynomial to be known as approximations. It is used in a subdivision framework combined with Newton iterations to achieve a near optimal complexity. An implementation of [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF] is described in [START_REF] Imbach | Implementation of a near-optimal complex root clustering algorithm[END_REF].

We also implemented our algorithm and made this implementation available to the community 4 as a package for Julia 5 . We compare our algorithm with state of the art solvers for solving triangular algebraic systems. We also consider the case of triangular systems obtained by triangularization with regular chains algorithms. Our implementation appears to be particularly efficient for systems with a small number of variables but with high degrees. Another interesting feature is the ability to solve locally, that is over a small polybox.

  Rémi's work is supported by the European Union's Horizon 2020 research and innovation programme No. 676541, NSF Grants # CCF-1563942, # CCF-1564132 and # CCF-1708884. Chee's work is supported by NSF Grants # CCF-1423228 and # CCF-1564132.

A multiset S is a pair (S, µ) where S is an ordinary set called the underlying set and µ : S → N assigns a positive integer µ(x) to each x ∈ S. Call µ(x) the multiplicity of x in S, and µ(S) := x∈S µ(x) the total multiplicity of S. Also, let |S| denote the cardinality of S. If |S|= 1, then S is called a singleton. We can form the union S ∪ S of two multisets with underlying set S ∪ S , and the multiplicities add up as expected.

https://github.com/rimbach/Ccluster.jl

https://julialang.org/