Clustering Complex Zeros of Triangular Systems of Polynomials

Rémi Imbach, Marc Pouget, Chee Yap

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)271-292
Number of pages22
JournalMathematics in Computer Science
Issue number2
StatePublished - Jun 2021


  • Certified algorithm
  • Complex root finding
  • Complex root isolation
  • Near-optimal root isolation
  • Oracle multivariable polynomial
  • Pellet’s theorem
  • Subdivision algorithm
  • Triangular polynomial system

ASJC Scopus subject areas

  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Clustering Complex Zeros of Triangular Systems of Polynomials'. Together they form a unique fingerprint.

Cite this