L'Agence nationale de la recherche Des projets pour la science

Translate this page in english

Blanc - SIMI 2 - Science informatique et applications (Blanc SIMI 2)
Edition 2013


DynA3S


Dynamique des algorithmes du pgcd : une approche Algorithmique, Analytique, Arithmétique et Symbolique

Dynamique des algorithmes du pgcd : une approche Algorithmique, Analytique, Arithmétique et Symbolique
Le but de ce projet est d'étudier des algorithmes de calcul de pgcd (plus grand commun diviseur) du point de vue des systèmes dynamiques. On considère un algorithme de pgcd comme un système dynamique discret en se concentrant sur les entrées entières. Nous sommes en premier lieu intéressés par le problème du calcul du pgcd de plusieurs entiers, mais une motivation supplémentaire provient également de la géométrie discrète.

Algorithmes dynamiques du pgcd
Le calcul du pgcd est l'une des opérations les plus basiques en théorie algorithmique des nombres. Si le calcul rapide du pgcd de deux entiers a été très largement étudié, la situation est plus contrastée concernant le fait d'avoir au moins 3 entrées.

Les systèmes dynamiques ont désormais prouvé leur pertinence en informatique, à la fois pour leur capacité de modélisation, et pour leur efficacité dans l'analyse d'algorithmes arithmétiques, typiquement, pour les algorithmes euclidiens. En effet, trouver une description d'un algorithme en termes de système dynamique permet une compréhension profonde du comportement probabiliste de ses paramètres, comme l'illustre l'algorithme d'Euclide (le père de tous les algorithmes selon Knuth) associé à la transformation de Gauss des fractions continues.

Nous avons deux objectifs principaux.

Premièrement, nous menons une étude extensive des algorithmes de pgcd qui sont décrits par un système dynamique. Nous prévoyons de construire des algorithmes efficaces de pgcd, de mener une analyse systématique (pire cas, analyse en moyenne et en distributions), et de comparer les performances de ces algorithmes selon un point de vue transverse qui combine une approche algorithmique, analytique, arithmétique et symbolique.

Deuxièmement, nous appliquons ces algorithmes en géométrie discrète pour l'étude des droites discrètes et des plans discrets, ce qui amène un point de vue supplémentaire concernant les comparaisons entre ces algorithmes.

Nous allons considérer tout particulièrement deux types d'algorithmes de pgcd, tous deux étant associés à des homographies par morceaux. La première famille est produite par des algorithmes de réduction dans les réseaux qui calculent des vecteurs courts, alors que la seconde famille rassemble des algorithmes de fractions continues multidimensionnels qui calculent de bonnes approximations rationnelles (comme l'algorithme de Jacobi-Perron).

Une approche algorithmique, analytique, arithmétique et symbolique
Nous allons comparer de façon systématique les algorithmes du pgcd et décrire leur paramètres principaux quand les entrées sont soit réelles (trajectoires génériques) ou entières (trajectoires tronquées). Nous menons cette étude simultanément selon deux points de vue, un point de vue discret, correspondant aux entrées rationnelles, et un point de vue continu, correspondant aux entrées réelles. Cela produit deux cadres dynamiques considérés pour eux-mêmes, mais aussi en interaction, selon la méthodologie de l'analyse dynamique qui combine des outils qui proviennent de la théorie ergodique et de la dynamique symbolique avec des outils de la combinatoire analytique et des outils algorithmiques.

Elle se décompose en 3 étapes principales. Premièrement, l'algorithme discret est étendu en un système dynamique continu, dont les exécutions sont décrites par des trajectoires particulières (les trajectoires des points rationnels). Deuxièmement, les paramètres principaux de l'algorithme sont étendus et étudiés dans ce contexte continu : l'étude des trajectoires particulières est remplacée par l'étude des trajectoires génériques. Enfin, on opère un transfert du continu au discret, où il est possible de prouver que le comportement probabiliste de la version discrète (trajectoires rationnelles) est très similaire au comportement continu (trajectoires génériques).

Ce projet rassemble des chercheurs qui vont travailler sur les algorithmes de type Euclide selon des approches comple´mentaires et diffe´rentes : syste`mes dynamiques (ergodique, symbolique, dynamique re´elle), algorithmes de re´duction dans les re´seaux, arithme´tique informatique, et analyse d'algorithmes et géométrie discrète. Les outils que nous utilisons sont algorithmiques (algorithmes d'Euclide, pour la réduction dans les réseaux et en géométrie discrète), dynamiques, issus de la combinatoire analytique, arithmétiques et diophantiens (exposants de Lyapounov) et
issus de la géométrie discrète.

Résultats

x

Perspectives

x

Productions scientifiques et brevets

x

Partenaires

GREYC Groupe de recherche en informatique, image, automatique et instrumentation de Caen

IRIF INSTITUT DE RECHERCHE EN INFORMATIQUE FONDAMENTALE

Aide de l'ANR 264 815 euros
Début et durée du projet scientifique octobre 2013 - 48 mois

Résumé de soumission

Le but de ce projet est d'étudier des algorithmes de calcul de pgcd (plus grand commun diviseur) du point de vue des systèmes dynamiques. On considère un algorithme de pgcd comme un système dynamique discret en se concentrant sur les entrées entières. Nous sommes en premier lieu intéressés par le problème du calcul du pgcd de plusieurs entiers. Mais une motivation supplémentaire provient également de la géométrie discrète, cadre dans lequel la compréhension des primitives basiques, les droites et les plans discrets, repose sur des algorithmes de type Euclide.

Nous avons deux objectifs principaux.
- Premièrement, nous menons une étude extensive des algorithmes de pgcd qui sont décrits par un système dynamique. Nous prévoyons de construire des algorithmes efficaces de pgcd, de mener une analyse systématique (pire cas, analyse en moyenne et en distributions), et de comparer les performances de ces algorithmes selon un point de vue transverse qui combine une approche algorithmique, analytique, arithmétique et symbolique.
-Deuxièmement, nous appliquons ces algorithmes en géométrie discrète pour l'étude des droites discrètes et des plans discrets, ce qui amène un point de vue supplémentaire concernant les comparaisons entre ces algorithmes.

Nous allons considérer tout particulièrement deux types d'algorithmes de pgcd, tous deux étant associés à des homographies par morceaux. La première famille est produite par des algorithmes de réduction dans les réseaux qui calculent des vecteurs courts, alors que la second famille rassemble des algorithmes de fractions continues multidimensionnels qui calculent de bonnes approximations rationnelles (comme l'algorithme de Jacobi-Perron).

Nous allons comparer de façon systématique ces algorithmes et décrire leur paramètres principaux quand les entrées sont soit réelles (trajectoires génériques) ou entières (trajectoires tronquées). Nous menons cette étude simultanément selon deux points de vue, un point de vue discret, correspondant aux entrées rationnelles, et un point de vue continu, correspondant aux entrées réelles. Cela produit deux cadres dynamiques considérés pour eux-mêmes,
mais aussi en interaction, selon la méthodologie de l'analyse dynamique. Cette méthodologie combine des outils qui proviennent de la théorie ergodique et de la dynamique symbolique avec des outils de la combinatoire analytique et des outils algorithmiques. Elle se décompose en 3 étapes principales.
-Premièrement, l'algorithme discret est étendu en un système dynamique continu, dont les exécutions sont décrites par des trajectoires particulières (les trajectoires des points rationnels).
-Deuxièmement, les paramètres principaux de l'algorithme sont étendus et étudiés dans ce contexte continu : l'étude des trajectoires particulières est remplacée par l'étude des trajectoires génériques.
-Enfin, on opère un transfert du continu au discret, où il est possible de prouver que le comportement probabiliste de la version discrète (trajectoires rationnelles) est très similaire au comportement continu (trajectoires génériques).


Un des buts de ce projet est d'établir des relations fortes entre les chercheurs qui travaillent dans les domaines impliqués et qui n'ont pas encore collaboré; au sein de ce projet, ils vont travailler sur le même objet --algorithmes de type Euclide-- selon des approches complémentaires et différentes : systèmes dynamiques (ergodique, symbolique, dynamique réelle), algorithmes de réduction dans les réseaux, arithmétique informatique, et analyse d'algorithmes.

Ce projet de 4 ans rassemble 16 chercheurs permanents, en informatique théorique et en mathématiques, 1 postdoc et 1 doctorant, pour un total de 320 personne.mois. Nous demandons également 2 postdocs (36 mois).

 

Programme ANR : Blanc - SIMI 2 - Science informatique et applications (Blanc SIMI 2) 2013

Référence projet : ANR-13-BS02-0003

Coordinateur du projet :
Madame Valérie BERTHE (INSTITUT DE RECHERCHE EN INFORMATIQUE FONDAMENTALE)

Site internet du projet : http://www.liafa.univ-paris-diderot.fr/dyna3s/

 

Revenir à la page précédente

 

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.