Real solving for positive dimensional systems

Philippe Aubry 1, 2 Fabrice Rouillier 2, 1 Mohab Safey El Din 2, 1
1 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
2 SPACES - Solving problems through algebraic computation and efficient software
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. Although numerous studies have been done on the subject, only a few number of efficient implementations exist. 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 zeros 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 which define it. From the output of our algorithm, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the real solutions. We report some 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, unlike the existing methods based on a similar strategy.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2002, 34 (6), pp.543-560. 〈10.1006/jsco.2002.0563〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00100982
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:53:17
Dernière modification le : jeudi 11 janvier 2018 - 06:27:20

Identifiants

Collections

Citation

Philippe Aubry, Fabrice Rouillier, Mohab Safey El Din. Real solving for positive dimensional systems. Journal of Symbolic Computation, Elsevier, 2002, 34 (6), pp.543-560. 〈10.1006/jsco.2002.0563〉. 〈inria-00100982〉

Partager

Métriques

Consultations de la notice

255