Real Solving for Positive Dimensional SystemsReport as inadecuate

Real Solving for Positive Dimensional Systems - Download this document for free, or read online. Document in PDF available to download.

1 LIP6 - Laboratoire d-Informatique de Paris 6 2 POLKA - Polynomials, Combinatorics, Arithmetic INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

Abstract : Finding one point on each semi-algebraically connected component of a real algebraic variety, or at least deciding if such a variety is empty or not, is a fundamental problem of computational real algebraic geometry. Even though numerous studies have been done on the subject, only a few number of efficient implementations exists. In this paper, we propose a new efficient and practical algorithm for computing such points. By studying the critical points of the restriction to the variety of the distance function to one well chosen point, we show how to provide a set of zero-dimensional systems whose zeroes contain at least one point on each semi-algebraically connected component of the studied variety, without any assumption neither on the variety smoothness or compactness for example nor on the system of equations that define it. Once such a result is computed, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the solutions. We have made experiments using a set of pure exact methods. The practical efficiency of our method is due to the fact that we do not apply any infinitesimal deformations, conversely to the existing methods based on similar strategy.

Keywords : real roots real algebraic variety connected components polynomial systems grobner bases triangular sets

Author: Philippe Aubry - Fabrice Rouillier - M. Safey El Din -



Related documents