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.

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.