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 -