Clustering Complex Zeros of Triangular Systems of Polynomials
Copyright policy )Clustering Complex Zeros of Triangular Systems of Polynomials
This paper gives the first algorithm for finding a set of natural $ε$-clusters of complex zeros of a triangular system of polynomials within a given polybox in $\mathbb{C}^n$, for any given $ε>0$. Our algorithm is based on a recent near-optimal algorithm of Becker et al (2016) for clustering the complex roots of a univariate polynomial where the coefficients are represented by number oracles. Our algorithm is numeric, certified and based on subdivision. We implemented it and compared it with two well-known homotopy solvers on various triangular systems. Our solver always gives correct answers, is often faster than the homotopy solver that often gives correct answers, and sometimes faster than the one that gives sometimes correct results.
Research report V6: description of the main algorithm updated
- French National Centre for Scientific Research France
- New York University United States
- New York University United States
- New York University United States
- University of Lorraine France
Computational Geometry (cs.CG), FOS: Computer and information sciences, near-optimal root isolation, Certified algor..., Numerical computation of solutions to systems of equations, triangular polynomial system, Oracle multivar..., Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral), complex root finding, Complex root fi..., [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], Triangular poly..., Complex root is..., Subdivision alg..., subdivision algorithm, Near-optimal ro..., oracle multivariable polynomial, Pellet’s theorem, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], complex root isolation, Pellet's theorem, Computer Science - Computational Geometry, certified algorithm, Computer Science - Mathematical Software, Mathematical Software (cs.MS)
Computational Geometry (cs.CG), FOS: Computer and information sciences, near-optimal root isolation, Certified algor..., Numerical computation of solutions to systems of equations, triangular polynomial system, Oracle multivar..., Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral), complex root finding, Complex root fi..., [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], Triangular poly..., Complex root is..., Subdivision alg..., subdivision algorithm, Near-optimal ro..., oracle multivariable polynomial, Pellet’s theorem, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], complex root isolation, Pellet's theorem, Computer Science - Computational Geometry, certified algorithm, Computer Science - Mathematical Software, Mathematical Software (cs.MS)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!