TY - JOUR

T1 - Clustering Complex Zeros of Triangular Systems of Polynomials

AU - Imbach, Rémi

AU - Pouget, Marc

AU - Yap, Chee

N1 - Funding Information:
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.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2021/6

Y1 - 2021/6

N2 - This paper gives the first algorithm for finding a set of natural ϵ-clusters of complex zeros of a regular triangular system of polynomials within a given polybox in Cn, for any given ϵ> 0. Our algorithm is based on a recent near-optimal algorithm of Becker et al. (Proceedings of the ACM on international symposium on symbolic and algebraic computation, 2016) for clustering the complex roots of a univariate polynomial where the coefficients are represented by number oracles. Our algorithm is based on recursive subdivision. It is local, numeric, certified and handles solutions with multiplicity. Our implementation is compared to with well-known homotopy solvers on various triangular systems. Our solver always gives correct answers, is often faster than the homotopy solvers that often give correct answers, and sometimes faster than the ones that give sometimes correct results.

AB - This paper gives the first algorithm for finding a set of natural ϵ-clusters of complex zeros of a regular triangular system of polynomials within a given polybox in Cn, for any given ϵ> 0. Our algorithm is based on a recent near-optimal algorithm of Becker et al. (Proceedings of the ACM on international symposium on symbolic and algebraic computation, 2016) for clustering the complex roots of a univariate polynomial where the coefficients are represented by number oracles. Our algorithm is based on recursive subdivision. It is local, numeric, certified and handles solutions with multiplicity. Our implementation is compared to with well-known homotopy solvers on various triangular systems. Our solver always gives correct answers, is often faster than the homotopy solvers that often give correct answers, and sometimes faster than the ones that give sometimes correct results.

KW - Certified algorithm

KW - Complex root finding

KW - Complex root isolation

KW - Near-optimal root isolation

KW - Oracle multivariable polynomial

KW - Pellet’s theorem

KW - Subdivision algorithm

KW - Triangular polynomial system

UR - http://www.scopus.com/inward/record.url?scp=85086662031&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086662031&partnerID=8YFLogxK

U2 - 10.1007/s11786-020-00482-0

DO - 10.1007/s11786-020-00482-0

M3 - Article

AN - SCOPUS:85086662031

VL - 15

SP - 271

EP - 292

JO - Mathematics in Computer Science

JF - Mathematics in Computer Science

SN - 1661-8270

IS - 2

ER -