Algorithmes efficaces en géométrie algébrique réelle

Mohab Safey El Din 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : En calcul scientifique, la résolution de problèmes algébriques non linéaires est une t\^ache importante et difficile. Dans plusieurs domaines de l'ingénierie, les problèmes algébriques encodent des contraintes géométriques sur des variables à valeurs réelles. C'est ainsi qu'il est fréquent de chercher à obtenir des informations sur l'ensemble des solutions réelles d'un système polynomial. La complexité théorique de la résolution de ces problèmes est souvent simplement exponentielle par rapport au nombre de variables. Les algorithmes initialement proposés dans cette classe de complexité se sont révélés inexploitables en pratique. Ainsi, jusque récemment, la plupart des logiciels mettent en œuvre des algorithmes dont la complexité est doublement exponentielle par rapport au nombre de variables. De plus, la nature non linéaire des problèmes considérés fait qu'il est difficile d'utiliser des méthodes numériques tout en garantissant l'exactitude du résultat fourni. Cela encourage l'utilisation de méthodes issues du calcul formel. Dans ce contexte, il s'agit alors de développer des algorithmes exacts, de contrôler adéquatement leur complexité, de les implémenter efficacement et cerner les spécifications les plus utiles. Ce cours présente des idées récentes guidées par des principes géométriques. Elles sont à la base d'algorithmes simplement exponentiels, parfois sous des hypothèses de généricité supplémentaires, et d'implémentations qui reflètent en pratique ces complexités. Nous étudierons plusieurs problèmes: calcul d'une solution d'un système d'équations algébriques multivariées, le problème de décider si deux points sont dans la même composante connexe et un cas particulier de l'élimination des quantificateurs.
Type de document :
Chapitre d'ouvrage
Informatique Mathématique Une photographie en 2015, CNRS Editions, 2015, 978-2-271-08791-1
Liste complète des métadonnées

https://hal.inria.fr/hal-01237922
Contributeur : Mohab Safey El Din <>
Soumis le : vendredi 4 décembre 2015 - 06:21:55
Dernière modification le : vendredi 31 août 2018 - 09:25:54

Identifiants

  • HAL Id : hal-01237922, version 1

Collections

Citation

Mohab Safey El Din. Algorithmes efficaces en géométrie algébrique réelle. Informatique Mathématique Une photographie en 2015, CNRS Editions, 2015, 978-2-271-08791-1. 〈hal-01237922〉

Partager

Métriques

Consultations de la notice

186