Mantzaflaris, GALAAD, INRIA Sophia Antipolis - Méditerranée.
Subdivision algorithms and the Continued Fraction expansion of real
roots of polynomial systems.
We present an overview of subdivision algorithms for the isolation of
the real roots of a system of multivariate polynomials. We introduce a
new algorithm of this family which treats equations in the monomial
basis and uses robust inclusion and exclusion criteria to reach the
solutions. Enveloping functions and preconditioning techniques are also
employed to reduce the domain of search. The resulting isolation boxes
have optimized rational coordinates, corresponding to the first terms of
the continued fraction expansion of the real roots. New complexity
bounds are provided for a simplified version of the algorithm. This is
joint work with B. Mourrain and E. Tsigaridas.
Last modified: Mon Mar 30 14:53:58 CEST 2009