Fédération de recherche Math-STIC de l'université Paris 13

FR3734

Journée scientifique 2016

La journée scientifique de la structure fédérative mathSTIC (LAGA-LIPN-L2TI) aura lieu 21 janvier 2016.

La journée aura lieu en amphi Fermat, Campus de Villetaneuse, Université Paris 13 (point numéroté 5 sur le plan du campus).

Cette journée sera l'occasion d'exposés scientifiques sur chacun des axes de la structure fédérative.

13h45 accueil / présentation de la structure fédérative et de ses activités (C. Fouqueré)
14h axe 3: Physique mathématique, Physique statistique, Combinatoire
  présentation de l'axe : Frédérique Bassino (LIPN) / Yueyun Hu (LAGA)
  exposés : Bénédicte Haas (LAGA) - The CRT is the scaling limit of large random dissections
                   Lionel Pournin (LIPN) - L'opération de flip dans les triangulations : du stockage de données à la topologie des surfaces
15h00 axe 1: Optimisation et Apprentissage appliqués aux contenus numériques
  présentation de l'axe : Azeddine Beghdadi (L2TI) / Roberto Wolfler-Calvo (LIPN)
  exposés : Caio Filippo Corro (LIPN) - Méthode lagrangienne pour les arborescences couvrantes avec application en traitement automatique des langues
                  Bilel Sdiri (L2TI) - Contrast enhancement method for stereo endoscopic images based on binocular just noticeable difference model
16h00 axe 2: Calcul haute-performance, systèmes distribués
  présentation de l'axe : Khaled Boussetta (L2TI) / Laurence Halpern (LAGA)
  exposés : Camille Coti (LIPN) - Exploiting Redundant Computation in Communication-Avoiding Algorithms for Algorithm-Based Fault Tolerance
                  Nadjib Achir (L2TI) - Path Planning of Unmanned Aerial Vehicles
16h45 Buffet / Cocktail
17h00

Conseil Scientifique

 

Résumés des exposés:

Bénédicte Haas (LAGA) : The CRT is the scaling limit of large random dissections

Une dissection du polygone régulier à n côtés est la graphe formé par le polygone et certaines de ses diagonales, avec la règle que deux diagonales ne peuvent se croiser qu'aux sommets du polygone. On s'intéresse ici au comportement asymptotiquement d'une dissection uniformément distribuée dans l'ensemble des dissections du polygone à n côtés. Nous verrons que multipliée par n^(-1/2) cette dissection uniforme converge vers un multiple du CRT brownien. Ce résultat se généralise à des mesures attribuant des poids de Boltzmann aux degrés des faces des dissections, lorsque ces poids décroissent suffisamment vite. Il s'agit d'un travail en collaboration avec Nicolas Curien et Igor Kortchemski.

 

Lionel Pournin (LIPN) : L'opération de flip dans les triangulations : du stockage de données à la topologie des surfaces

Les triangulations sont des objets très populaires dans de nombreux domaines comme la géométrie algorithmique, la combinatoire, la topologie, la cristallographie, l'analyse numérique, etc. En pratique, elles sont construites en utilisant des opérations locales appelées des flips qui les modifient de manière minimale.
Cet exposé donnera un aperçu de l'utilisation des flips dans plusieurs contextes très différents, en particulier en géométrie algorithmique et en topologie des surfaces. Il sera question de caractériser la structure géométrique d'un ensemble de triangulation induite par l'opération de flip.
Plusieurs résultats concernant cette structure seront donnés au long de l'exposé, et je présenterai quelques problèmes ouverts liés à la notion de flip, qui rassemblent les chercheurs en mathématiques et en informatique.

 

Caio Filippo Corro (LIPN) : Méthode lagrangienne pour les arborescences couvrantes avec application en traitement automatique des langues

Nous nous intéressons au calcul des arborescences couvrantes de poids maximum avec deux contraintes structurelles : degré de bloc (block degree) et bonne imbrication (well-nestedness). Ces contraintes sont motivées par des problèmes d’analyse syntaxique en traitement automatique des langues (TAL) dans lesquels une phrase est représentée sous forme d’une arborescence couvrante dans un graphe orienté. Nous proposons une formulation du problème en PLNE ainsi qu’une relaxation lagrangienne de celle-ci. Le problème relâché correspond à l’arborescence couvrante de poids maximal pouvant être efficacement calculée grâce à l’algorithme d’Edmonds.

 

Bilel Sdiri (L2TI) : Contrast enhancement method for stereo endoscopic images based on binocular just noticeable difference model

Endoscopic image enhancement has become a very popular research field due to the success of minimally invasive interventions and the innovation of new technological treatment and diagnosis tools such as stereoscopic laparoscopes and the wireless capsule endoscopy. In this talk we present a contrast enhancement method for stereo endoscopic images taking into consideration some of these specificities, the depth information, the binocular vision and the organs salient features. The proposed method produces stereo endoscopic images with sharper details, without introducing any halo effect or overshooting. The observers reported as well a more depth feeling and less visual fatigue when perceiving the enhanced stereo endoscopic images.

 

Camille Coti (LIPN) : Exploiting Redundant Computation in Communication-Avoiding Algorithms for Algorithm-Based Fault Tolerance


Communication-avoiding algorithms allow redundant computations to minimize the number of inter-process communications. In this paper, we propose to exploit this redundancy for fault-tolerance purpose. We illustrate this idea with QR factorization of tall and skinny matrices, and we evaluate the number of failures our algorithm can tolerate under different semantics.

 

Nadjib Achir (L2TI) : Path Planning of Unmanned Aerial Vehicles

Drones or UAVs (Unmanned Aerial Vehicles) are unmanned flying machines capable of carrying out more or less autonomous mission. Their earliest development was intended to the military use. Typical missions are the reconnaissance and the surveillance of wide and/or abroad territories. The technological progress in different domains that are related to UAVs, such as, advances in aeronautical, robotic, batteries and computer science have recently extended the economical perspectives toward the civil market. Beside the gained popularity of drones as toys for entertainment, there are already several successful uses of UAVs for civil applications. One can refer to traffic monitoring in highways, prevention of forests fires, inspection of buildings and structures or data gathering for environment, for agriculture or for mining. These progress has also attracted the research community and several new research topics were raised. In this presentation we are interested in path planning using UAV.

 

Journée scientifique 2014

La journée scientifique du pôle mathSTIC (LAGA-LIPN-L2TI) aura lieu 9 avril 2014.

La journée aura lieu en amphi Copernic, Campus de Villetaneuse, Université Paris 13 (point numéroté 7 sur le plan du campus).

Cette journée sera l'occasion d'exposés scientifiques sur chacun des axes du pôle.

8h45 accueil
9h présentation du pôle et de ses activités (C. Fouqueré)
9h10 axe 1: Optimisation et Apprentissage appliqués aux contenus numériques
  Joseph Leroux (LIPN) - Analyse syntaxique des langues naturelles par combinaison de grammaires algébriques et décomposition lagrangienne
  Gabriel Dauphin (L2TI) - Utilisation de dictionnaires spécifiques à chaque bloc pour la compensation de disparité en compression d'image stéréoscopiques
10h10 axe 2: Calcul haute-performance, systèmes distribués
  Benoit Lizé (LAGA) - Solveur Direct Rapide: H-Matrix. Parallélisation à l'aide de graphe de tâches et applications industrielles
  Laure Petrucci (LIPN) - Protocoles réseaux : de la modélisation à la vérification formelle
11h10 pause café
11h30 axe 3: Physique mathématique, Physique statistique, Combinatoire
  Thomas Fernique (LIPN) - Marches aléatoires biaisées dans des espaces de pavages
  Muriel Livernet (LAGA) - Questions combinatoires ouvertes en théorie des opérades
12h45 Buffet

Axe 1 :
- Joseph Leroux (LIPN)
Titre: Analyse syntaxique des langues naturelles par combinaison de grammaires algébriques et décomposition lagrangienne

La décomposition fait désormais partie de la /trousse à outils/ formelle en traitement automatique des langues, en particulier en analyse syntaxique (Rush et Collins, 2010). Elle permet en effet de pallier le problème majeur de la taille de l'espace de recherche causé par l'ambiguïté massive du langage naturelle, que la programmation dynamique ne permet pas toujours de résoudre, tout en donnant des /certificats d'optimalité/ aux solutions retournées, contrairement aux approximations à base de seuil habituellement utilisées.

La plupart des travaux dans ce domaine se sont consacrés soit à l'analyse syntaxique en dépendances d'ordre supérieur soit à la modélisation de tâches jointes (analyse syntaxique et étiquetage en partie du discours par exemple), et il n'existe pas de travaux sur la décomposition pour l'analyse en constituants.

Nous présentons un algorithme qui permet de calculer la meilleure analyse à partir de plusieurs grammaires pondérées qui peuvent engendrer des langages différents mais "proches" modulo certaines opérations simples (renommage des nœuds et débinarisation des règles). Notre méthode repose sur la superposition partielle des meilleures solutions de chaque analyseur. Nous utilisons un algorithme de décomposition à base de sous-gradient projeté inspiré de l'algorithme d'inférence dans les champs markoviens aléatoires de (Komodakis et al, 2007). Nous montrons expérimentalement que cette méthode permet d'améliorer les performances d'un système d'analyse syntaxique déjà très "compétitif". Nous obtenons des résultats /état-de-l'art/ sur le Penn Treebank, corpus de référence en analyse syntaxique, avec un F-score supérieur à 92,4.

- Gabriel Dauphin (L2TI)
Titre: "Utilisation de dictionnaires spécifiques à chaque blocs pour la compensation de disparité en compression d'image stéréoscopiques".

Axe 2 :
- Laure Petrucci (LIPN).
Titre : Network protocols: from modelling to formal verification

Résumé :
Designing network protocols is difficult task that must lead to reliable communications wrt. the targeted application.
They are often described lengthy and verbose RFC documents, which may contain inconsistencies or lead to unexpected behaviour.
Alternatively, prototype tools may implement communication protocols which seem to behave correctly in practice.
However, since they are at the core of critical applications, it is necessary to guarantee some level of reliability.
To do so, a formal model can be designed, and then essential properties model-checked.
We will present our experience with such protocols modelling and verification, show the benefits of the approach and open up new research perspectives for better design and parameters tuning.

- Benoit Lizé (LAGA) :
Titre : Solveur Direct Rapide: H-Matrix. Parallélisation à l'aide de graphe de tâches et applications industrielles.

Résumé : La discrétisation d'équations intégrales par la méthode des éléments finis de frontière (BEM) mène à la résolution de grands systèmes linéaires pleins, dont le nombre d'inconnues $n$ dépasse largement $10^6$ dans les problèmes industriels. Cette résolution est soit directe, avec un coût en $O(n^3)$, soit itérative, pour un coût de $O(n^2 × n_{iter})$. Dans les deux cas, ce coût devient prohibitif pour des problèmes de grande taille. La méthode multipôle rapide (FMM) [1] amena des avancées spectaculaires dans les années 2000 (particulièrement dans une implémentation parallèle [2]), réduisant la complexité d'un solveur itératif à $O(n log^2(n) n_{iter})$. Elle hérite néanmoins des inconvénient usuels des solveurs itératifs (convergence, grand nombre de seconds membres).

Nous présentons ici l'application de la méthode des H-Matrices, permettant de réaliser un solveur direct avec une complexité $O(n log^α(n))$ [3]. Cette méthode, basée sur des principes similaires à la FMM (approximations hiérarchiques, séparation des variables) se formalise par des algorithmes naturellement récursifs. Ceux-ci sont très irréguliers en terme de consommation mémoire et temps de calcul, et possèdent des dépendances non triviales entre les étapes de calcul, ce qui rend leur parallélisation délicate [4]. Nous donnerons une parallélisation efficace de ces algorithmes, basée sur un formalisme récent de graphe de tâches, au-dessus d'un moteur d'exécution, ici StarPU [5] [6]. La description plane de ces algorithmes sous la forme de graphe acyclique orienté (DAG) exprimant les contraintes d'exécution permet une parallélisation efficace, en mémoire partagée et distribuée, ainsi que sur architectures hybrides.

Nous présenterons des applications industrielles à des problèmes d'électromagnétisme et acoustique aujourd'hui inaccessibles au calcul par d'autres méthodes.

Références :

[1] E. Darve "The fast multipole method: numerical implementation". Journal of Computational Physics, 2000, 160(1), pp. 195-240
[2] G. Sylvand, "La méthode multipôle rapide en électromagnétisme: performances, parallélisme, applications". Thèse de doctorat, ENPC, 2002
[3] L. Grasedyck, W. Hackbusch, "Construction and Arithmetics of H-Matrices", Computing, 2003, 70(4), pp. 295-334
[4] R. Kriemann, "Parallel H-Matrix Arithmetics on Shared Memory Systems", Computing, 2005, 74(3), pp. 273-297
[5] B. Lizé, G. Sylvand, E. Agullo and S. Thibault, "A task-based H-Matrix solver on multicore architectures", SciCADE 2013
[6] B. Lizé, G. Sylvand, "H-Matrix vs. FMM: Fast Methods applied to BEM solvers", WAVES 2013, 11th International Conference on Mathematical and Numerical Aspects of Waves

Axe 3 :
* Thomas Fernique (LIPN) :
Marches aléatoires biaisées dans des espaces de pavages.

On considère l'ensemble des pavages par losanges d'une région bornée donnée du plan. On se déplace dans cet espace grâce à l'opération élémentaire qui consiste à tourner d'un demi-tour un hexagone formé de trois losanges (flip). Ceci permet de définir une marche aléatoire (on effectue aléatoirement un flip), qu'on s'autorise à biaiser en fonction de l'environnement local de l'hexagone tourné. On se demande si la chaîne de Markov ainsi définie est ergodique, et le cas échéant à quoi ressemble sa mesure stationnaire et à quelle vitesse on s'en approche. Ce problème est motivé par l'étude de la formation des quasicristaux.


* Muriel Livernet (LAGA)
"Questions combinatoires ouvertes en théorie des opérades"

Les opérades sont un outil pour traiter des structures algébriques, comme les algèbre associatives, commutatives, les algèbres de Lie, etc...
De manière générale on se pose la question de savoir si une opérade peut être décrite par générateurs et relations. Si l'on a quelques outils en main pour permettre de dire s'il y a des relations ou non (cas d'une opérade libre), en général on n'en n'a pas pour compter le nombre de générateurs. Après avoir défini les opérades, je donnerai deux exemples illustrant ce problème.

Journée de lancement

Les laboratoires LAGA, LIPN, L2TI organisent la journée de lancement le 18 avril 2013 du *pôle mathSTIC*.

La journée aura lieu en amphi A, Campus de Villetaneuse, Université Paris 13.

Cette journée permettra de présenter le pôle ainsi que les 3 axes définis actuellement, leurs projets en cours, leurs orientations, au travers d'exposés scientifiques.

9h30 accueil
9h45 présentation du pôle (C. Fouqueré)
10h axe 2 (L. Halpern)
  C. Coti - Architectures émergentes et passage à l'échelle d'applications parallèles
  N. Achir  - Déploiement de réseaux sans fil
  C. Japhet - Méthodes de décomposition de domaine espace-temps
  F. Benkhaldoun  -  Calculs performants pour la simulation d'écoulements à fronts raides
12h buffet
13h15 axe 3 (A. Sportiello)
  B. Rittaud    Mots circulaires
  A. Tanasa     Physique combinatoire : algèbres de Hopf combinatoires en théories quantiques de champs
  P. Marchal    combinatoire et aleas
15h15 pause café
15h30 axe 1 (R. Wolfler-Calvo)
  L. Létocart  - Les algorithmes de flots à la rescousse
  B. Matei - Compression d'images avec contrôle de qualité : au delà de JPEG2000
  K. Boussetta - Améliorer la mobilité grâce aux Systèmes de Transport Intelligents
17h30 fin

 

Nadjib Achir(L2TI) : Déploiement de réseaux sans fil
Résumé : Dans cet exposé, nous présentons des méthodes de résolution exactes et heuristiques pour le déploiement des réseaux sans fil. Nous nous focaliserons sur deux catégories de réseaux sans fil à savoir les réseaux de capteurs sans fil statiques ainsi que les réseaux maillés sans fil. L'objectif est de trouver les positions quasi-optimales des nœuds sans fil dans une zone de déploiement donnée, tout en garantissant certaines contraintes liées au type du réseaux, telles que le coût de déploiement, la probabilité de détection, la connectivité et la durée de vie du réseau pour les réseaux de capteurs sans fil ou encore la qualité de service et l’équité pour les réseaux sans fil maillés.

Fayssal Benkhaldoun (LAGA) : Calculs performants pour la simulation d'écoulements à fronts raides
Résumé :Nous exposons dans cette présentation une série de problèmes issus de la physique et régis par des systèmes d'équations aux dérivées partielles. La caractéristique commune à ces problèmes est la forte non linéarité des équations, la présences de fronts raides et une disparité des échelles spatiales et temporelles. La résolution numérique des ces problèmes nécessite donc le recours a des algorithmes de haute performance aussi bien du point de vue des méthodes mathématiques utilises que du point de vue de l'optimisation informatique. Nous montrerons des résultats obtenus en 2D  grâce a la technique de l'adaptation de maillages, dans le domaine de l'environnement et de la physique des plasma, et évoquerons la perspective du recours au calcul parallèle en vue du passages aux calculs 3D.

Camille Coti (LIPN) : Architectures émergentes et passage à l'échelle d'applications parallèles
Résumé: Durant cet exposé, je présenterai quelques exemples d'architectures hiérarchiques des machines actuelles et émergentes à grande échelle. J'en dériverai les défis auxquels font face les applications de calcul numérique, et présenterai quelques exemples de solutions envisagées pour y faire face. Enfin, je présenterai deux exemples de noyaux de calcul numérique utilisant des algorithmes de nouvelle génération et pouvant servir de brique de base à de nombreuses applications scientifiques.

Caroline Japhet (LAGA) : Méthodes de décomposition de domaine espace-temps
Résumé: Dans de nombreuses simulations de phénomènes physiques, le domaine de calcul est en fait une union de plusieurs sous-domaines avec différentes propriétés physiques et dont les échelles spatiales et temporelles peuvent être très différentes. C'est le cas pour la simulation du transport de contaminants autour d'un site de stockage de déchets nucléaires ou du couplage >océan-atmosphère. Nous présentons des méthodes de décomposition de domaine permettant d'avoir différentes grilles en temps et en espace, adaptées aux différentes échelles temporelles et spatiales, dans les sous-domaines. Ces techniques sont bien adaptées au calcul haute performance et aux systèmes distribués.

Adrian Tanasa (LIPN) : Physique combinatoire : algèbres de Hopf combinatoires en théories quantiques de champs
Résumé :  La Physique Combinatoire est un domaine émergent, à la frontière entre la Physique Mathématique et la Combinatoire, que cette dernière soit Analytique, Algébrique ou autre. A l'intérieur de cette vaste thématique on peut identifier la description algébrique de la combinatoire de la renormalisation en théories quantiques des champs (commutatives, non-commutatives ou bien des modèles de tenseurs aléatoires) : cela représente un des projets scientifiques du Pôle Math-STIC de l'UP13-SPC. Dans cet exposé je passerai rapidement en revue certains résultats obtenus récemment par différents membres du LIPN et du LAGA et je concluerai ensuite avec quelques perspectives pour des travaux en commun à l'intérieur de notre Pôle.