Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

No description available.

Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1.) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1.

La simulation haute-fidélité des coeurs de réacteurs nucléaires nécessite une évaluation précise du flux neutronique dans le coeur du réacteur. Ce flux est modélisé par l’équation de Boltzmann ou équation du transport neutronique. Dans cette thèse, on s’intéresse à la résolution de cette équation par la méthode des ordonnées discrètes (SN) sur des géométries cartésiennes. Cette méthode fait intervenir un schéma d’itérations à source, incluant un algorithme de balayage sur le domaine spatial qui regroupe l’essentiel des calculs effectués. Compte tenu du très grand volume de calcul requis par la résolution de l’équation de Boltzmann, de nombreux travaux antérieurs ont été consacrés à l’utilisation du calcul parallèle pour la résolution de cette équation. Jusqu’ici, ces algorithmes de résolution parallèles de l’équation du transport neutronique ont été conçus en considérant la machine cible comme une collection de processeurs mono-coeurs indépendants, et ne tirent donc pas explicitement profit de la hiérarchie mémoire et du parallélisme multi-niveaux présents sur les super-calculateurs modernes. Ainsi, la première contribution de cette thèse concerne l’étude et la mise en oeuvre de l’algorithme de balayage sur les super-calculateurs massivement parallèles modernes. Notre approche combine à la fois la vectorisation par des techniques de la programmation générique en C++, et la programmation hybride par l’utilisation d’un support d’exécution à base de tâches: PaRSEC. Nous avons démontré l’intérêt de cette approche grâce à des modèles de performances théoriques, permettant également de prédire le partitionnement optimal. Par ailleurs, dans le cas de la simulation des milieux très diffusifs tels que le coeur d’un REP, la convergence du schéma d’itérations à source est très lente. Afin d’accélérer sa convergence, nous avons implémenté un nouvel algorithme (PDSA), adapté à notre implémentation hybride. La combinaison de ces techniques nous a permis de concevoir une version massivement parallèle du solveur SN Domino. Les performances de la partie Sweep du solveur atteignent 33.9% de la performance crête théorique d’un super-calculateur à 768 cores. De plus, un calcul critique d’un réacteur de type REP 900MW à 26 groupes d’énergie mettant en jeu 1012 DDLs a été résolu en 46 minutes sur 1536 coeurs. / High-fidelity nuclear reactor core simulations require a precise knowledge of the neutron flux inside the reactor core. This flux is modeled by the linear Boltzmann equation also called neutron transport equation. In this thesis, we focus on solving this equation using the discrete ordinates method (SN) on Cartesian mesh. This method involves a source iteration scheme including a sweep over the spatial mesh and gathering the vast majority of computations in the SN method. Due to the large amount of computations performed in the resolution of the Boltzmann equation, numerous research works were focused on the optimization of the time to solution by developing parallel algorithms for solving the transport equation. However, these algorithms were designed by considering a super-computer as a collection of independent cores, and therefore do not explicitly take into account the memory hierarchy and multi-level parallelism available inside modern super-computers. Therefore, we first proposed a strategy for designing an efficient parallel implementation of the sweep operation on modern architectures by combining the use of the SIMD paradigm thanks to C++ generic programming techniques and an emerging task-based runtime system: PaRSEC. We demonstrated the need for such an approach using theoretical performance models predicting optimal partitionings. Then we studied the challenge of converging the source iterations scheme in highly diffusive media such as the PWR cores. We have implemented and studied the convergence of a new acceleration scheme (PDSA) that naturally suits our Hybrid parallel implementation. The combination of all these techniques have enabled us to develop a massively parallel version of the SN Domino solver. It is capable of tackling the challenges posed by the neutron transport simulations and compares favorably with state-of-the-art solvers such as Denovo. The performance of the PaRSEC implementation of the sweep operation reaches 6.1 Tflop/s on 768 cores corresponding to 33.9% of the theoretical peak performance of this set of computational resources. For a typical 26-group PWR calculations involving 1.02×1012 DoFs, the time to solution required by the Domino solver is 46 min using 1536 cores.

Les travaux de recherche présentés dans ce manuscrit concernent l'application des méthodes multi-niveaux pour la simulation numérique des écoulements incompressibles turbulents dans le cadre d'une approximation Volumes Finis avec placement des inconnues sur grilles décalées (Harlow et Welch), ainsi que le développement d'une nouvelle méthode de type frontière immergée sur maillage cartésien pour la simulation numérique d'écoulements autour d'obstacles. Les écoulements considérés dans cette étude sont bidimensionnels.

Cette thèse concerne l'utilisation de modèles fonctionnels dans le test de circuits intégrés complexes. Dans la première partie, des vecteurs de test sont générés pour les automates d'états finis a partir de leurs spécifications de synthèse. Un premier ensemble de vecteurs de test est calcule en parcourant tous les arcs du graphe de contrôle. Les valeurs d'entrées non spécifiées sur les transitions sont fixées afin d'accroitre la couverture. Il est montre que ce test a une excellente couverture par rapport a sa longueur. Les fautes résiduelles sont détectées par une methode de distinction sur les modèles machine juste machine fausse. La deuxième partie est consacrée au test hiérarchisé de circuits complexes. Les vecteurs de test locaux aux blocs sont justifies vers les entrées primaires et propages en avant vers les sorties primaires en utilisant des variables symboliques et des modèles fonctionnels pour les blocs traverses. Des techniques originale de propagation retardée permettent de restreindre le nombre d'échecs des propagations. Un prototype en prolog a été expérimenté

On s’intéresse à la simulation d’écoulements compressibles multi-matériaux et, notamment, aux interactions fluide/structure dans les régimes transitoires et en dynamique rapide. Le but est de pouvoir décrire l’évolution de matériaux de lois de comportement très différentes à l’aide d’un modèle unique. Les milieux sont seulement différenciés par leurs équations d’état et sont séparés par une interface dite sharp. Les matériaux peuvent être des fluides ou des solides élastiques et sont soumis à de grandes déformations. Le modèle est écrit dans le formalisme eulérien. Le schéma numérique est résolu sur des grilles cartésiennes pour des simulations en trois dimensions.Une extension du modèle permet de décrire les déformations plastiques des solides. / We are interested in the simulation of compressible multimaterial flows and especially influid/structure interactions in transient states and fast dynamics. We aim to describe the evolution of materials of very different constitutive laws with an unified model. The materials are only differentiated by their own constitutive laws and are separated by a sharp interface. They can be as well fluids or elastic solids and under go large de formations. The model is written in the Eulerian framework. The numerical scheme is solved on Cartesian grids for simulations in three dimensions. An extension of the elastic model is added to describe the plastic deformations of solids.

Ce travail porte sur le développement d'un code numérique tridimensionnel pour la simulation d'entrées en tunnels de trains à grande vitesse en vue de proposer des solutions afin de réduire les nuisances occasionnées. L'écoulement de l'air est modélisé par les équations d'Euler instationnaires. Ces équations sont discrétisées à l'aide d'une formulation en volumes finis et résolues grâce à un schéma solveur de Riemann approché, d'ordre supérieur, particulièrement adapté à la propagation d'ondes. Pour gérer le mouvement relatif du train par rapport au tunnel, une méthode de maillage glissant est utilisée avec un traitement conservatif des faces aux niveaux des jonctions de maillages. Le domaine est ainsi décomposé en plusieurs sous-domaines, maillés indépendamment avec un mailleur cartésien automatique basé sur un maillage surfacique triangulaire. Pour réduire le domaine, et donc le temps de calcul, et accélérer la stabilisation de l'écoulement avant l'entrée du train, des conditions aux limites non réflectives sont implémentées. La méthodologie est validée sur plusieurs cas tests. Une étude paramétrique de l'influence d'un auvent à l'entrée du tunnel sur le gradient de l'onde de compression pression initiale est effectuée. Les paramètres de cette étude sont la forme, la longueur et la section de l'auvent. Enfin, l'effet d'ouvertures dans l'auvent est simulé.

Dans le but d’améliorer le comportement thermo-mécanique des aubes de turbine présentes dans les moteurs d’avion développés par SAFRAN, il est nécessaire de mettre au point un nouveau matériau composite. Le procédé de fabrication de ce matériau est complexe et requiert une densification par voie liquide divisée en deux étapes. Cette thèse s’intéresse à la modélisation numérique de la première étape appelée Slurry Cast/APS.Celle-ci consiste en l’injection et le confinement, dans la préforme fibreuse, de particules préalablement mises en suspension. Pour cela, nous avons développé à l’échelle des fibres,un modèle qui utilise les équations de Navier-Stokes incompressibles et monophasiques ,l’équation de Phillips [Phillips et al., 1992] et une loi rhéologique [Krieger, 1972]. Après validation des résultats numériques par comparaison avec des résultats expérimentaux [Hampton et al., 1997] et théoriques [Belfort et al., 1994], le modèle est utilisé pour simuler l’écoulement autour de géométries de tissage proches du matériau étudié. / In order to improve thermo-mechanical behavior of tubine blades in SAFRAN engines plane, a new composite material is necessary. The manufacturing process to obtain this composite is intricate and requires a two steps fluid densification process. This thesis focuses on numerical simulation of the first one called Slurry Cats/APS. In this step, suspended particles are introducted and captured in the reinforcement. For that purpose,we carry out a model at fiber scale, using Navier-Stokes equations in incompressible and monophasic formulation, Phillips equations [Phillips et al., 1992] and a rheological law [Krieger, 1972]. After validation step consisting in a comparison of computational results with experiments [Hampton et al., 1997] and theorical law [Belfort et al., 1994], this model has been used to simulate flow around geometries similar to those encountered in our composite material.

On associe à chaque variété algébrique définie sur R un complexe de cochaînes filtré, qui calcule la cohomologie à supports compacts et coefficients dans Z_2 de ses points réels. Ce complexe filtré est additif pour les inclusions fermées et acyclique pour la résolution des singularités, et est unique à quasi-isomorphisme filtré près. Il est représenté par la filtration duale de la filtration géométrique sur les chaînes semi-algébriques à supports fermés définie par McCrory and Parusiński, et induit une suite spectrale qui calcule la filtration par le poids sur la cohomologie à supports compacts. Cette suite spectrale est un invariant naturel qui contient les nombres de Betti virtuels. On montre que le produit cartésien de deux variétés nous permet de comparer le produit de leurs complexe de poids et suite spectrale respectifs avec ceux du produit, et on prouve que les produits cap et cup en cohomologie et homologie sont filtrés par rapport à ces filtrations par le poids réelles. / We associate to each algebraic variety defined over R a filtered cochain complex, which computes the cohomology with compact supports and Z_2-coefficients of the set of its real points. This filtered complex is additive for closed inclusions and acyclic for resolution of singularities, and is unique up to filtered quasi-isomorphism. It is represented by the dual filtration of the geometric filtration on semialgebraic chains with closed supports defined by McCrory and Parusiński, and leads to a spectral sequence which computes the weight filtration on cohomology with compact supports. This spectral sequence is a natural invariant which contains the additive virtual Betti numbers. We then show that the cross product of two varieties allows us to compare the product of their respective weight complexes and spectral sequences with those of their product, and prove that the cup and cap products in cohomology and homology are filtered with respect to the real weight filtrations.