Bienvenue sur la page du projet Dyna3S :
Ce projet est financé par l'Agence Nationale de la Recherche, ANR Programme Blanc SIMI 2.
Projet ANR-13-BS02-0003
Coordinatrice : Valérie Berthé
Durée : 60 mois, du 15-10-2013 au 15-10-2018
Partenaires
- Partenaire 1. Valérie Berthé, LIAFA, Univ. Paris Diderot Paris 7
- Pôle 2. Brigitte Vallée, GREYC, Université de Caen Basse Normandie
Résumé
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, à savoir les 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,
- analyse d'algorithmes.
Projets apparentés
- Dynalco Advances in Analytic Combinatorics: dynamical combinatorics, and applications to number theory, information theory and cryptography, DYNALCO 2013-2014, STIC-AmSud.
- LAREDA Lattice Reduction Algorithms: Dynamics, Probabilities, Experiments, Applications, ANR 2007.
Comparaisons Une page autour de la comparaison des algorithmes de fractions continues.