Ce mémoire présente mes activités de recherche dans le domaine de la mécanique statistique des systèmes désordonnés, en particulier sur les modèles de champ moyen à connectivité finie. Ces modèles présentent de nombreuses transitions de phase dans la limite thermodynamique, avec des applications tant pour la physique des verres que pour leurs liens avec des problèmes d'optimisation de l'informatique théorique. Leur comportement sous l'effet de fluctuations quantiques est aussi discuté, en lien avec des perspectives de calcul quantique.

Ce travail s'intéresse à la conception sous contraintes de dispositifs électromagnétiques à l'aide de modèles analytiques. Après avoir présenté le contexte de conception en génie électrique, et les problèmes inhérents au dimensionnement sous contraintes, notamment celui des systèmes d'équations implicites, l'étude présente une nouvelle architecture orientée objet pour le dimensionnement à l'aide de modèles analytiques. L'objectif est de créer un environnement souple et modulaire pour manipuler les équations analytiques de façon à utiliser toute l'information qu'elles contiennent. On veut par exemple ré-orienter le modèle étudié ou calculer les dérivées partielles symboliques des paramètres de sortie, ceci afin d'effectuer de la propagation de contraintes, du solver ou de l'optimisation sous contraintes. Un prototype informatique implantè est présenté.

Ce mémoire d'Habilitation à Diriger des Recherches (HDR) retrace dix années de recherche en tant que maître de conférences, autour de modèles d'EDP appliqués à des écoulements de fluides. On y trouve aussi bien des aspects analyse mathématique, qu'analyse numérique, algorithmique ou encore calcul et mise en oeuvre informatique. Les principaux modèles d'EDP abordés sont les équations de Navier-Stokes ou Stokes surface libre (micro-fluidique, glaciologie), les équations de St-Venant ou asymptotique "shallow" (hydraulique fluviale, glaciologie). L'orientation de ces études vers les thématiques applicatives a conduit à élaborer des modèles numériques potentiellement applicables aux problèmes réels posés. Ainsi, les aspects calibration de modèles, optimisation, identification, analyse de sensibilité et assimilation de données (via le contrôle optimal) y sont largement représentés. En termes de réalisation de logiciels prototypes, sont présentés un code d'hydraulique fluviale (inondations) dédié à l'analyse de sensibilité, l'assimilation variationnelle de données et le couplage, un code surface libre d'impact de gouttelettes (2D axisymétrique ALE) et un code d'optimisation de forme appliqué à l'électro-capillarité. <br /> Le premier chapitre présente des analyses mathématiques et analyse de schémas éléments finis basées sur des troncatures. Un second chapitre décrit un cadre mathématique et algorithmique pour l'optimisation de forme, avec applications à un modèle Navier-Stokes - thermique radiative et à une gouttelette électrifiée (électro-capillarité). Un troisième chapitre traite de la modélisation numérique de la dynamique d'une gouttelette sur un substrat solide. La dynamique de la ligne triple y est décrite à l'aide du modèle de Shikhmurzaev. Dans un quatrième chapitre sont présentés plusieurs travaux autour d'écoulements fluviaux et zones d'inondations (St-Venant 1.5D-2D, schémas volumes finis). Les processus de calibrage de modèles, de couplage et d'assimilation variationnelle de données constituent une grand part des travaux. Des applications à des écoulements réels avec données non standards (trajectoires lagrangiennes, image satellite) démontrent la potentialité des méthodes développées. Le dernier chapitre traite des travaux récemment initiés et tout particulièrement ceux relatifs aux calottes polaires (Stokes non-Newtonien et équations asymptotiques). Parmi les difficultés mathématiques soulevées figurent la réduction de modèles (asymptotique, réduction d'ordre), le couplage, la sensibilité des modèles aux erreurs et aux paramètres, et enfin l'assimilation de données et le calibrage.

Les algorithmes Branch and Bound (B&B) sont attractifs pour la résolution exacte de problèmes d'optimisation combinatoire (POC) par exploration d'un espace de recherche arborescent. Néanmoins, ces algorithmes sont très gourmands en temps de calcul pour des instances de problèmes de grande taille (exemple : benchmarks de Taillard pour FSP) même en utilisant le calcul sur grilles informatiques [Mezmaz et al., IEEE IPDPS'2007]. Le calcul massivement parallèle fourni à travers les plates-formes de calcul hétérogènes d'aujourd'hui [TOP500 ] est requis pour traiter effi cacement de telles instances. Le dé fi est alors d'exploiter tous les niveaux de parallélisme sous-jacents et donc de repenser en conséquence les modèles parallèles des algorithmes B&B. Dans cette thèse, nous nous attachons à revisiter la conception et l'implémentation des ces algorithmes pour la résolution de POC de grande taille sur (larges) plates-formes de calcul multi-coeurs et multi-GPUs. Le problème d'ordonnancement Flow-Shop (FSP) est considéré comme étude de cas. Une étude expérimentale préliminaire sur quelques grandes instances du FSP a révélé que l'arbre de recherche est hautement irrégulier (en forme et en taille) et très large (milliards de milliards de noeuds), et que l'opérateur d'évaluation des bornes est exorbitant en temps de calcul (environ 97% du temps de B&B). Par conséquent, notre première contribution est de proposer une approche GPU avec un seul coeur CPU (GB&B) dans laquelle seul l'opérateur d'évaluation est exécuté sur GPU. L'approche traite deux dé fis: la divergence de threads et l'optimisation de la gestion de la mémoire hiérarchique du GPU. Comparée à une version séquentielle, des accélérations allant jusqu'à ( 100) sont obtenues sur Nvidia Tesla C2050. L'analyse des performances de GB&B a montré que le surcoût induit par le transfert des données entre le CPU et le GPU est élevé. Par conséquent, l'objectif de la deuxième contribution est d'étendre l'approche (LL-GB&B) a fin de minimiser la latence de communication CPU-GPU. Cet objectif est réalisé grâce à une parallélisation à grain fin sur GPU des opérateurs de séparation et d'élagage. Le défi majeur relevé ici est la divergence de threads qui est due à la nature fortement irrégulière citée ci-dessus de l'arbre exploré. Comparée à une exécution séquentielle, LL-GB&B permet d'atteindre des accélérations allant jusqu'à ( 160) pour les plus grandes instances. La troisième contribution consiste à étudier l'utilisation combinée des GPUs avec les processeurs multi-coeurs. Deux scénarios ont été explorés conduisant à deux approches: une concurrente (RLL-GB&B) et une coopérative (PLL-GB&B). Dans le premier cas, le processus d'exploration est eff ectué simultanément par le GPU et les coeurs du CPU. Dans l'approche coopérative, les coeurs du CPU préparent et transfèrent les sous-problèmes en utilisant le streaming CUDA tandis que le GPU eff ectue l'exploration. L'utilisation combinée du multi-coeur et du GPU a montré que l'utilisation de RLL-GB&B n'est pas bénéfi que et que PLL-GB&B permet une amélioration allant jusqu'à (36%) par rapport à LL-GB&B. Sachant que récemment des grilles de calcul comme Grid5000 (certains sites) ont été équipées avec des GPU, la quatrième contribution de cette thèse traite de la combinaison du calcul sur GPU et multi-coeur avec le calcul distribué à grande échelle. Pour ce faire, les diff érentes approches proposées ont été réunies dans un méta-algorithme hétérofigène qui sélectionne automatiquement l'algorithme à déployer en fonction de la con figuration matérielle cible. Ce méta-algorithme est couplé avec l'approche B&B@Grid proposée dans [Mezmaz et al., IEEE IPDPS'2007]. B&B@Grid répartit les unités de travail (sous-espaces de recherche codés par des intervalles) entre les noeuds de la grille tandis que le méta-algorithme choisit et déploie localement un algorithme de B&B parallèle sur les intervalles reçus. L'approche combinée nous a permis de résoudre à l'optimalité et e fficacement les instances (20 20) de Taillard.

Mon travail de thèse consiste à comprendre une géométrie introduite par Cartan en 1933 \cite{Cartan1933}. \textit{La géométrie de Finsler} présente de nombreuses analogies avec cette théorie. Nous avons étudié les grandes lignes de cette géométrie. Le point de départ de Cartan qui est analogue à celui qui conduit à la géométrie finslerienne, est d'imaginer l'espace comme étant un lieu ''d'éléments de contact'', un élément étant la donnée d'un point $M\in\mathcal{M}^n$ et d'un hyperplan $H$ passant par ce point et orienté dans l'espace tangent $T_M\mathcal{M}^n$. Nous avons ainsi défini \textit{la géométrie de Cartan fondée sur la notion d'aire} dans un premier temps, je me suis intéressé à la notion d'orthogonalité dans cette géométrie. La méthode de Cartan pour étudier le problème d'équivalence est un outil puissant qui est implicitement décrit dans cette géométrie. Nous avons ensuite appliqué cette méthode aux équations de Monge-Ampère (cas elliptique), en s'inspirant des travaux de R. Bryant, D. Grossmann et P. Griffiths. Plusieurs faits ne sont pas encore suffisamment clairs pour disposer d'un dictionnaire évident entre ces travaux et celui donné par Cartan.

Résumé : Cette thèse comporte 8 chapitres. Le chapitre 1 est une introduction aux problématiques rencontrées sur les marchés énergétiques : fréquence d'intervention faible, coûts de transaction élevés, évaluation des options spread. Le chapitre 2 étudie la convergence de l'erreur de couverture d'une option call dans le modèle de Bachelier, pour des coûts de transaction proportionnels (modèle de Leland-Lott) et lorsque la fréquence d'intervention devient infinie. Il est prouvé que cette erreur est bornée par une variable aléatoire proportionnelle au taux de transaction. Cependant, les démonstrations de convergence en probabilité demandent des régularités sur les sensibilités assez restrictives en pratique. Les chapitres suivants contournent ces obstacles en étudiant des convergences presque sûres. Le chapitre 3 développe tout d'abord de nouveaux outils de convergence presque sûre. Ces résultats ont de nombreuses conséquences sur le contrôle presque sûr de martingales et de leur variation quadratique, ainsi que de leurs incréments entre deux temps d'arrêt généraux. Ces résultats de convergence trajectorielle sont connus pour être difficiles à obtenir sans information sur les lois. Par la suite, nous appliquons ces résultats à la minimisation presque sûre de la variation quadratique renormalisée de l'erreur de couverture d'une option de payoff général (cadre multidimensionnel, payoff asiatique, lookback) sur une large classe de temps d'intervention. Une borne inférieure à notre critère est trouvée et une suite minimisante de temps d'arrêt optimale est exhibée : il s'agit de temps d'atteinte d'ellipsoïde aléatoire, dépendant du gamma de l'option. Le chapitre 4 étudie la convergence de l'erreur de couverture d'une option de payoff convexe (dimension 1) en prenant en compte des coûts de transaction à la Leland-Lott. Nous décomposons l'erreur de couverture en une partie martingale et une partie négligeable, puis nous minimisons la variation quadratique de cette martingale sur une classe de temps d'atteintes générales pour des Deltas vérifiant une certaine EDP non-linéaire sur les dérivées secondes. Nous exhibons aussi une suite de temps d'arrêt atteignant cette borne. Des tests numériques illustrent notre approche par rapport à une série de stratégies connues de la littérature. Le chapitre 5 étend le chapitre 3 en considérant une fonctionnelle des variations discrètes d'ordre Y et de Z de deux processus d'Itô Y et Z à valeurs réelles, la minimisation étant sur une large classe de temps d'arrêt servant au calcul des variations discrètes. Borne inférieure et suite minimisant sont obtenues. Une étude numérique sur les coûts de transaction est faite. Le chapitre 6 étudie la discrétisation d'Euler d'un processus multidimensionnel X dirigé par une semi-martingale d'Itô Y . Nous minimisons sur les temps de la grille de discrétisation un critère quadratique sur l'erreur du schéma. Nous trouvons une borne inférieure et une grille optimale, ne dépendant que des données observables. Le chapitre 7 donne un théorème limite centrale pour des discrétisations d'intégrale stochastique sur des grilles de temps d'atteinte d'ellipsoïdes adaptées quelconque. La corrélation limite est conséquence d'asymptotiques fins sur les problèmes de Dirichlet. Dans le chapitre 8, nous nous intéressons aux formules d'expansion pour les options sur spread, pour des modèles à volatilité locale. La clé de l'approche consiste à conserver la propriété de martingale de la moyenne arithmétique et à exploiter la structure du payoff call. Les tests numériques montrent la pertinence de l'approche.

Dans cette thèse, nous montrons que les optimisations source-à-source sont un moyen efficace pour générer des programmes irréguliers ou parallèles performants à partir d'une implémentation. Après avoir présenté l'évolution des architectures des processeurs, nous proposons deux méthodes distinctes. La première pour extraire des codelets d'un programme irréguliers, les optimiser et prédire les performances du programme modifié. L'autre pour limiter l'impact des problèmes d'alignements dus à la vectorisation ou aux conflits de bancs. Nous présentons aussi différentes techniques de parallélisation, l'une générant des codelets parallèles, l'autre ordonnançant un graphe de taches sur un système hétérogène.

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations <em>n</em>-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

La simulation de la neutronique d'un coeur de réacteur nucléaire est basée sur l'équation du transport des neutrons, et un calcul de criticité conduit à un problème à valeur propre. Parmi les méthodes de résolution déterministes, l'approximation de la diffusion est souvent utilisée. Le solveur MINOS basé sur une méthode d'éléments finis mixte duale, a montré son efficacité dans la résolution de ce problème. Afin d'exploiter les ordinateurs parallèles, et de réduire les coûts en temps de calcul et en mémoire, nous proposons dans ce mémoire deux méthodes de décomposition de domaine pour la résolution du problème à valeur propre de la diffusion des neutrons sous forme mixte duale. La première méthode est inspirée d'une méthode de synthèse modale : la solution est cherchée dans une base constituée d'un nombre fini de modes propres locaux calculés par MINOS sur des sous-domaines recouvrants. La deuxième méthode est un algorithme itératif de Schwarz modifié qui utilise des sous-domaines non recouvrants et des conditions de Robin aux interfaces entre sous-domaines. A chaque itération, le problème est résolu par MINOS sur chaque sous-domaine avec des conditions aux interfaces calculées à partir des solutions sur les sous-domaines adjacents à l'itération précédente. Les itérations permettent la convergence simultanée de la décomposition de domaine et du problème à valeur propre. Les résultats numériques obtenus sur des modèles 2D et 3D de coeurs réalistes montrent la précision et l'efficacité en parallèle de ces deux méthodes.

Dans cette thèse, nous avons considéré des problèmes de minimisation de fonctionnelles relatives à des objets géométriques en dimension 2 et 3 sous contraintes de bord. Nous considérons d'abord le cas des corps de largeur constante en dimension 2 et nous redémontrons le théorème de Blaschke-Lebesgue par la théorie du contrôle optimal en utilisant le principe de Pontryagin. Nous étudions aussi le problème de la minimisation du volume dans la classe des corps de largeur constante en dimension 3 et à symétrie de révolution. Par le principe de Pontryagin, nous obtenons des conditions nécessaires sur un minimiseur. Nous étudions également le problème de minimisation de l'aire dans la classe des rotors d'un polygone à n côtés, ce qui constitue une généralisation du problème précédent. Par le principe de Pontryagin, nous démontrons qu'un minimiseur est une réunion finie d'arcs de cercles de rayon r_i où les r_i prennent des valeurs quantifiées. Nous étudions plus spécifiquement certaines propriétés des rotors réguliers en s'intéressant à leur optimalité locale pour la fonctionnelle d'aire, et pour un certain type de déformations admissibles. Par le théorème de Kuhn-Tucker, nous généralisons au cas des rotors un résultat de Firey en montrant que les rotors réguliers du triangle équilatéral sont des maxima locaux de l'aire, et que les rotors réguliers des polygones réguliers à n>4 côtés, sont des points selles de l'aire. Enfin, nous étudions le problème de minimisation du volume en dimension 3 dans la classe des corps de largeur constante. Nous introduisons d'abord un espace fonctionnel prenant en compte la contrainte de convexité et celle de largeur. Puis nous en déduisons des conditions d'optimalité faibles, vérifiées par le solide de Meissner, dont on conjecture depuis 1934 qu'il minimise le volume dans cette classe.