Sites Inria

English version

Equipe de recherche SPACES

Systèmes polynomiaux, arithmétiques, calculs efficaces et sûrs

  • Responsable : Paul Zimmermann
  • Centre(s) de recherche : CRI Nancy - Grand Est
  • Domaine : Systèmes symboliques
  • Thème : Structures algébriques et géométriques, algorithmes

Présentation de l'équipe

L'objectif principal du projet de recherche SPACES est la résolution de systèmes polynomiaux, à coefficients rationnels ou dans des corps finis, en dimension zéro (nombre fini de solutions complexes ou dans une clôture algébrique) ou en dimension positive (nombre infini de solutions).

Parmi les domaines d'application où des résultats ont déjà été obtenus, on peut citer la simulation, la commande et le diagnostic de machines-outils parallèles, des problèmes de mécanique céleste, la cryptographie (dans le cas des corps finis), la compression d'image et la biophysique. Un objectif de l'équipe est d'étendre significativement cette liste de domaines d'application.

La "résolution" de tels systèmes consiste à donner une description de l'ensemble des solutions qui soit précise et adaptée aux besoins des utilisateurs. Dans le cas de la dimension zéro, il s'agit généralement des valeurs numériques approchées de toutes les solutions situées dans un certain corps (complexes, réels, ...), avec une borne garantie de l'erreur. Dans le cas général, l'objectif ultime est la description complète de la topologie de l'ensemble des solutions. Celle-ci étant aujourd'hui à peu près inaccessible, il faut déterminer des classes de problèmes ou de questions, qui soient à la fois effectivement calculables et utiles aux applications.

En raison de la complexité au moins exponentielle de ces problèmes, leur résolution efficace passe évidemment par l'amélioration des algorithmes, mais aussi par l'utilisation de techniques d'implantation efficaces et le développement d'arithmétiques adaptées (entiers et flottants de grande précision, intervalles, mais aussi polynômes, infinitésimaux algébriques, etc).

Axes de recherche

  • Résolution algébrique
  • Solutions réelles
  • Arithmétiques
  • Méthodes hybrides

Une part importante de l'activité de l'équipe consiste en le développement de logiciels robustes et efficaces permettant de résoudre les problèmes algébriques.

Logiciels

Relations industrielles et internationales

  • ACI Cryptologie ``PolyCrypt''
  • Coopération avec le groupe Magma de l'Université de Sydney

Mots-clés : Systèmes polynomiaux Arithmétique Calcul symbolique Calcul numerique Calcul hybride Bases de GrÖbner Résolution algébrique Solutions réelles

Suivez Inria