Current continuation methods for finding all solutions to systems of polynomial equations first compute all complex solutions, and then sieve them to find the real solutions. This method is not optimal in that number of paths to be followed may not reflect the actual number of real solutions. This problem is particularly acute for fewnomial systems, a class of systems whose number of real solutions is typically much smaller than their number of complex solutions. Recent work has established a new bound for the number of real solutions to a system of fewnomials, by transforming the system of polynomials into an equivalent system of master functions on a hyperplane complement, called the gale dual system. Sturmfels observed that the method used to establish those bounds, the Khovanskii-Rolle Theorem, could be the basis of a continuation algorithm to compute all real solutions, which has the additional feature that the path continuation only follows real solutions. In this talk, I will sketch the main ideas in this new algorithm. This will also include a sketch of the proof of these new fewnomial bounds, and some of the continuation issues which arisen in an implementation of the algorithm. We remark that the complexity of this algorithm depends on the ambient (real dimension) and the fewnomial bound, and not on the number of complex solutions. The implementation of the algorithm is joint work with Daniel J. Bates, while the fewnomial bounds and reduction to Gale systems is work with Frédéric Bihan and Bates.
Dans cette exposé nous étudions le problème d'évolution associé à l'équation de Monge-Kantorovich pour le transport optimale de masse. Il est aussi appelé le modèle de Prigozhin pour le tas de sable. Nous démontrons les résultats d'existence et d'unicité de solution dans le cas où les données sont des mesures et nous montrons comment appliquer des méthodes de dualités pour la résolution numérique. Enfin nous présentons quelques résultats de simulations numérique.
The purpose of this communication is to discuss the simulation of a free surface compressible flow between two fluids, typically air and water. We use a two fluid model with the same velocity, pressure and temperature for both phases. In such a model, the free surface becomes a thin three dimensional zone. The present model has at least three advantages: (i) the free-surface treatment is completely implicit; (ii) it can naturally handle wave breaking and other topological changes in the flow; (iii) one can easily vary the Equation of States (EOS) of each fluid (in principle, one can even consider tabulated EOS). Moreover, our model is unconditionally hyperbolic for reasonable EOS. First, we present the physical context of our study. Then, we introduce the governing equations and we give some rationales on the limit of this model to the classical free surface model. Finally, we present our numerical method based on a flux scheme which is, in particular, constructed to model accurately impacts of waves on walls. Since our code is designed for unstructured meshes, it can easily treat complex geometries (for example, liquified natural gas carrier tank). This communication will conclude with the presentation of different simulation results on the sloshing of a liquid in a closed container.
Cf le site idoine: http://choco.pps.jussieu.fr/events.
Le vitrier ou le carreleur exploite un phénomène que nous nous proposons d'analyser : une petite incision dans un matériau cassant permet de générer des concentrations de contraintes localisées. En termes mathématiques, nous considèrerons une perturbation singulière de la géométrie d'un domaine et présenterons l'analyse asymptotique de la solution de l'équation de Laplace dans ce domaine perturbé. Nous montrerons comment utiliser cette analyse pour le calcul numérique et le cas de plusieurs perturbations. Ces travaux sont réalisés dans le cadre de l'ANR Macadam.
Comme le montrent les publicités dans les magazines (multi-coeur par-ci, hyperthread par-là), la tendance des architectures des ordinateurs est à la parallélisation, et l'on commence donc dans le grand public à parler de programmation avec des threads. Du côté des machines de calcul scientifique, on mélange en fait allègrement ces technologies de manière hiérarchique pour aboutir à de véritables cathédrales, sur lesquelles on exécute une armée de threads. Cependant, pour obtenir une exécution efficace (et donc économiser du temps, des machines ou de l'énergie), il est indispensable de distribuer de manière raisonnée ces threads sur ces machines. La tâche est d'autant plus ardue que les threads peuvent en créer d'autres, éventuellement de manière irrégulière. Durant ma thèse, j'ai proposé la notion de /bulles/, qui regroupent de manière récursive les threads et apportent ainsi une certaine structure aux applications de calcul scientifique. En modélisant par ailleurs les machines de calcul sous forme d'un arbre, on ramène ainsi notre problème à la mobilité des bulles et threads sur cet arbre. Une boîte à outil permet alors d'implémenter des algorithmes de placement/redistribution pour les appliquer à des applications bien concrètes. On peut alors observer des gains de performances de l'ordre de 20 à 40% par rapport à un ordonnancement classique ! Je débuterai mon exposé en expliquant quelques détails architecturaux importants par rapport à l'efficacité de l'exécution des threads d'une application. J'introduirai alors ce que j'entends par ordonnancement'',placement'' et ``migration'' des threads et bulles. Je présenterai ensuite la boîte à outils au travers de quelques exemples, et l'on pourra discuter notamment de la ressemblance intriguante avec des ambients.
On considère un type de métriques riemanniennes singulières qui apparait naturellement en théorie du contrôle : soient X et Y deux champs de vecteurs sur une variété M de dimension 2. Si X et Y forment partout une famille libre, ils définissent naturellement sur M une métrique riemannienne dont ils forment un champ de bases orthonormées. Quand X et Y ne sont plus partout linéairement indépendants, sous certaines conditions génériques de non intégrabilité de la distribution qu'ils engendrent, ils définissent sur M une métrique sous-riemannienne sur une distribution de rang non constant, qu'on peut voir comme une métrique riemannienne singulière. Ces structures font apparaître des phénomènes intéressants, en particulier pour ce qui concerne les liens entre courbure, lieu conjugué et topologie de la variété. Je présenterai, lors de cet exposé, un résultat du type ``formule de Gauss-Bonnet'' démontré par Agrachev, Boscain et Sigalotti et expliquerai les difficultés liées à sa démonstration dans le cas ou la métrique présente des singularités de type Martinet.
Cet exposé, est une partie d’un article en cours, en collaboration avec {\it Latifa Faouzi} (Fes et Casablanca) et se compose de deux parties indépendantes.
PARTIE I: $k$-algèbre libre sur un monoïde.
On considère un corps commutatif $k$ et un monoïde (= demi-groupe commutatif et unitaire) $M$. On désigne par $k[M]$ la $k$-algèbre sur le monoïde $M$, i.e. l’espace vectoriel sur $k$ ayant $M$ comme base, c’est alors aussi un anneau puisque $M$ est stable par produit. L’exemple type étant l’algèbre des polynômes sur $k$. Le corps $k$ étant fixé, on montre plusieurs propriétés de la classe des algèbres sur un monoïde. Par exemple $k[X] x k[Y]$ est une $k$-algèbre libre sur un monoïde. On développe aussi une classe plus large où le produit de deux élements de $M$ est soit $0$, soit un élement de $M$.
PARTIE II: Demi-treillis compact. Dans cette partie, les monoïdes ne sont pas unitaires. On considère un triplet $(L,O,.)$ où $(L,O)$ est un espace compact séparé, $(L,.)$ est un monoïde idempotent (mais sans unité). On suppose que l’application $(x,y) -> x. y$ est continue. En interprétant $x . y$ comme l’infimum de $x$ et de $y$, $(L,.)$ est un (inf-)demi-treillis et $.$ est continue. Noter que $L$ est alors un ensemble ordonné en posant $x \leq y$ ssi $x . y = x$. On montre quelques propriété de cette classe de structures. Par exemple, une telle structure possède un plus petit élément $0$ et toute partie non vide et filtrante supérieurement possède un supremum. La topologie est alors déterminée par l’ordre: une sous-base de la topologie est formée d’élements de la forme $U_x := { y \in L : y \geq x }$ et $L \setminus U_x$ où $x$ est un élément “compact” de $L$. Ces notions de demi-treillis compacts apparaissent lors de l’étude des domaines et des treillis algébriques.
PARTIE III: Le lien. Si on considère le corps $k = {0,1}$ ayant deux éléments et le monoïde $M$ idempotent, alors $k[M]$ est une algèbre de Boole, dont l’espace des ultrafiltres (ou des idéaux maximaux) est un demi-treillis compact et “réciproquement”.
Bibliographie:
[1] Bourbaki N.: Eléments de mathématiques, Algèbre, Chapitres 1--3, Hermann, 1970.
[2] Lang S.: Algebra, Addision-Wiesley Pub, 1970.
[3] Gierz, G., Hofmann K. H., Keimel K., Lawson J. D., Mislove M. and Scott D. S.: Continuous lattices and domains, Encyclopedia of Mathematics and its Applications, 93. Cambridge University Press, Cambridge, 2003, 591 pp.
L'objectif de cet exposé est de présenter le contexte et les motivations ayant conduit à mon sujet de thèse : Géométrie multirésolution des objets discrets bruités. On commencera par présenter quelques outils classiques autour des droites discrètes et leurs applications à l'estimation de quantités géométriques sur des formes discrètes. L'extension de ces outils aux formes discrètes bruitées sera ensuite abordée. On en déduira les quelques axes de recherche qui seront explorés dans ma thèse.
On présente un ensemble d'études traitant de la modélisation numérique d'écoulements à surface libre. Les équations considérées peuvent être des équations de Navier-Stokes surface libre (résolues par des schémas éléments finis en formulation ALE - caractéristiques) ou encore leurs dérivées asymptotiques type ``shallow'' (non visqueux, schémas volumes finis). La première partie traite de la modélisation des plaines d'inondations et porte tout particulièrement sur les aspects inverses tels que la calibration des modèles, leur couplage faible simultané, l'identification de paramètres et l'assimilation de données. Ces approches sont basées sur les méthodes de contrôle optimal et des équations adjointes. La seconde partie traite d'une modélisation de la dynamique de la ligne triple en microfluidique (modèle de Shikhmurzaev). On y présente aussi bien des aspects analyse mathématique qu'élaboration d'algorithmes et illustration avec l'étalement d'une gouttelette sur un substrat solide. La troisième partie, dont les travaux viennent seulement de commencer, traite d'écoulements glaciaires multi-échelles. On y retrouve alors un ensemble d'ingrédients mathématiques, numériques et logiciels abordés dans les deux applications précédentes.
Cet exposé fera un survol du domaine de la topologie des images, ou digital topology'', ainsi que quelques-unes de ses applications. L'espace image est vu comme un sous-ensemble de Z^n, une forme dans une image est un sous-ensemble de Z^n. Nous présenterons ainsi les approches graphes, cellulaires et intermédiaires. On verra qu'une des difficultés est de définir ce qu'est une surface (discrète'' donc) dans ces espaces, afin de retrouver les propriétés classiques de l'espace euclidien. Ensuite, nous montrerons quelques algorithmes effectifs d'extraction de surfaces, avec quelques applications. Si le temps le permet, nous nous intéresserons au calcul effectif de l'homologie, afin d'obtenir des invariants topologiques sur les formes discrètes.
Ce séminaire donnera les liens entre un problème de recouvrement des entiers et la combinatoire des mots afin d'étudier la conjecture de Fraenkel. Cette conjecture a été formulée dans le cadre de la théorie des nombres il y a maintenant plus de 30 ans. Elle prétend que pour k > 2 entier fixé, il y a une unique façon de recouvrir les entiers par $k$ suites de Beatty avec des fréquences deux à deux distinctes. Ce problème peut être exprimé en termes de combinatoire des mots de la façon suivante: pour un alphabet à k lettres, il existe une unique suite équilibrée avec des fréquences de lettres deux à deux distinctes qui est exactement la suite de Fraenkel notée $(F r_k )^{omega}$ où F r_k = F r_{k-1} k F r_{k-1}, avec F r_3 = 1213121. Cette conjecture est prouvée pour k = 3, 4, 5, 6 d'après les travaux de Altman, Gaujal, Hordijk et Tijdeman ainsi que dans d'autres cas particuliers. Dans ce séminaire, nous présenterons donc une synthèse sur ce sujet et la résolution de la conjecture dans un cas particulier.
TBA
Le travail présenté est une collaboration avec Marius Mitrea, professeur à University of Missouri, Columbia. On s’intéresse aux équations de Navier-Stokes non compressibles pour des conditions au bord de Dirichlet dans des domaines bornés en dimension 3, sans imposer a priori de régularité au bord. La première difficulté est de donner un sens aux équations dans un tel cadre. On montre ensuite l’existence locale de solutions régulières à la Kato pour des données initiales dans un espace critique. Dans le cas où le domaine est àbord lipschitzien, les solutions obtenues ont la meme régularité que dans le cas de domaines réguliers. La preuve repose sur la caractérisation du domaine de l’opérateur de Stokes, ou plutot de ses puissances fractionnaires. http://junon.u-3mrs.fr/monniaux/chambery08.pdf
Dans cet exposé, nous donnons une caractérisation très complète des courbes singulières pour une distribution D générique (la notion de généricité utilisée ici est très forte car générique signifie appartenant à un ouvert dense de l'ensemble des distributions, dont le complémentaire est de codimension arbitrairement grande). Nous établirons que, si D est générique, toute courbe singulière admet un unique relèvement extrémal par le principe du maximum de Pontryagin et que le contrôle associé à la trajectoire se calcule presque partout par feedback à partir de ce relèvement. Ceci nous permet de montrer en particulier que, si D n'est pas de dimension 2, une métrique sous-riemannienne (D,g) générique n'admet pas de trajectoire minimisante singulière, ce qui à son tour a de nombreuses conséquences sur la régularité de la distance et des sphères sous-riemanniennes.
Un automate cellulaire est un modèle de calcul parallèle synchrone, qui consiste en une juxtaposition d'automates d'état fini (cellules) dont l'état évolue dans le temps en fonction de celui de leurs voisins. Malgré la simplicité de cette règle locale, des comportements très variés peuvent être observés dans l'évolution d'une population de cellules.
Nous présentons ici quelques notions topologiques décrivant ces dynamiques. Nous nous intéressons en particulier à la nilpotence, qui correspond à un comportement ultimement stable. Nous en donnons une caractérisation utilisant la trace, qui est le mot infini représentant la suite des états pris par une cellule donnée.
Après avoir exposé quelques motivations de ce travail dans la sphère de l'optimisation : méthodes de gradient, minimisation alternée..., nous montrerons comment les inégalités de Lojasiewicz peuvent se caractériser dans un cadre relativement général, ie celui des fonctions convexes à un carré près dans les espaces de Hilbert. On examinera en particulier les reformulations en termes de ``bornes d'erreurs'', de lipschitzianité de l'application sous-niveau, de talweg ou encore de flots de sous-gradient. Quelques résultats positifs et négatifs concernant les fonctions convexes seront évoqués.