La performance d'un algorithme sur une architecture donnée dépend à la fois de la vitesse à laquelle le processeur effectue des opérations à virgule flottante (flops) et de la vitesse d'accès à la mémoire et au disque. Etant donné que le coût de la communication est beaucoup plus élevé que celui des opérations arithmétiques, celle-là forme un goulot d'étranglement dans les algorithmes numériques. Récemment, des méthodes de sous-espace de Krylov basées sur les méthodes 's-step' ont été développées pour réduire les communications. En effet, très peu de préconditionneurs existent pour ces méthodes, ce qui constitue une importante limitation. Dans cette thèse, nous présentons le préconditionneur nommé ''Communication-Avoiding ILU0'', pour la résolution des systèmes d’équations linéaires (Ax=b) de très grandes tailles. Nous proposons une nouvelle renumérotation de la matrice A ('alternating min-max layers'), avec laquelle nous montrons que le préconditionneur en question réduit la communication. Il est ainsi possible d’effectuer « s » itérations d’une méthode itérative préconditionnée sans communication. Nous présentons aussi deux nouvelles méthodes itératives, que nous nommons 'multiple search direction with orthogonalization CG' (MSDO-CG) et 'long recurrence enlarged CG' (LRE-CG). Ces dernières servent à la résolution des systèmes linéaires d’équations de très grandes tailles, et sont basées sur l’enrichissement de l’espace de Krylov par la décomposition du domaine de la matrice A. / The performance of an algorithm on any architecture is dependent on the processing unit’s speed for performing floating point operations (flops) and the speed of accessing memory and disk. As the cost of communication is much higher than arithmetic operations, and since this gap is expected to continue to increase exponentially, communication is often the bottleneck in numerical algorithms. In a quest to address the communication problem, recent research has focused on communication avoiding Krylov subspace methods based on the so called s-step methods. However there are very few communication avoiding preconditioners, and this represents a serious limitation of these methods. In this thesis, we present a communication avoiding ILU0 preconditioner for solving large systems of linear equations (Ax=b) by using iterative Krylov subspace methods. Our preconditioner allows to perform s iterations of the iterative method with no communication, by applying a heuristic alternating min-max layers reordering to the input matrix A, and through ghosting some of the input data and performing redundant computation. We also introduce a new approach for reducing communication in the Krylov subspace methods, that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on the domain decomposition of the graph of A. The enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and to parallelizable algorithms with less communication, with respect to Krylov methods. We discuss two new versions of Conjugate Gradient, multiple search direction with orthogonalization CG (MSDO-CG) and long recurrence enlarged CG (LRE-CG).

Le sujet de ce travail de thèse est l’application de la méthode de caractéristiques longues (MOC) pour résoudre l’équation du transport des neutrons pour des géométries à trois dimensions extrudées. Les avantages du MOC sont sa précision et son adaptabilité, le point faible était la quantité de ressources de calcul requises. Ce problème est même plus important pour des géométries à trois dimensions ou le nombre d’inconnues du problème est de l’ordre de la centaine de millions pour des calculs d’assemblage.La première partie de la recherche a été dédiée au développement des techniques optimisées pour le traçage et la reconstruction à-la-volé des trajectoires. Ces méthodes profitent des régularités des géométries extrudées et ont permis une forte réduction de l’empreinte mémoire et une réduction des temps de calcul. La convergence du schéma itératif a été accélérée par un opérateur de transport dégradé (DPN) qui est utilisé pour initialiser les inconnues de l’algorithme itératif and pour la solution du problème synthétique au cours des itérations MOC. Les algorithmes pour la construction et la solution des opérateurs MOC et DPN ont été accélérés en utilisant des méthodes de parallélisation à mémoire partagée qui sont le plus adaptés pour des machines de bureau et pour des clusters de calcul. Une partie importante de cette recherche a été dédiée à l’implémentation des méthodes d’équilibrage la charge pour améliorer l’efficacité du parallélisme. La convergence des formules de quadrature pour des cas 3D extrudé a aussi été explorée. Certaines formules profitent de couts négligeables du traitement des directions azimutales et de la direction verticale pour accélérer l’algorithme. La validation de l’algorithme du MOC a été faite par des comparaisons avec une solution de référence calculée par un solveur Monte Carlo avec traitement continu de l’énergie. Pour cette comparaison on propose un couplage entre le MOC et la méthode des Sous-Groupes pour prendre en compte les effets des résonances des sections efficaces. Le calcul complet d’un assemblage de réacteur rapide avec interface fertile/fissile nécessite 2 heures d’exécution avec des erreurs de quelque pcm par rapport à la solution de référence.On propose aussi une approximation d’ordre supérieur du MOC basée sur une expansion axiale polynomiale du flux dans chaque maille. Cette méthode permet une réduction du nombre de mailles (et d’inconnues) tout en gardant la même précision.Toutes les méthodes développées dans ce travail de thèse ont été implémentées dans la version APOLLO3 du solveur de transport TDT. / The topic of our research is the application of the Method of Long Characteristics (MOC) to solve the Neutron Transport Equation in three-dimensional axial geometries. The strength of the MOC is in its precision and versatility. As a drawback, it requires a large amount of computational resources. This problem is even more severe in three-dimensional geometries, for which unknowns reach the order of tens of billions for assembly-level calculations.The first part of the research has dealt with the development of optimized tracking and reconstruction techniques which take advantage of the regularities of three-dimensional axial geometries. These methods have allowed a strong reduction of the memory requirements and a reduction of the execution time of the MOC calculation.The convergence of the iterative scheme has been accelerated with a lower-order transport operator (DPN) which is used for the initialization of the solution and for solving the synthetic problem during MOC iterations.The algorithms for the construction and solution of the MOC and DPN operators have been accelerated by using shared-memory parallel paradigms which are more suitable for standard desktop working stations. An important part of this research has been devoted to the implementation of scheduling techniques to improve the parallel efficiency.The convergence of the angular quadrature formula for three-dimensional cases is also studied. Some of these formulas take advantage of the reduced computational costs of the treatment of planar directions and the vertical direction to speed up the algorithm.The verification of the MOC solver has been done by comparing results with continuous-in-energy Monte Carlo calculations. For this purpose a coupling of the 3D MOC solver with the Subgroup method is proposed to take into account the effects of cross sections resonances. The full calculation of a FBR assembly requires about 2 hours of execution time with differences of few PCM with respect to the reference results.We also propose a higher order scheme of the MOC solver based on an axial polynomial expansion of the unknown within each mesh. This method allows the reduction of the meshes (and unknowns) by keeping the same precision.All the methods developed in this thesis have been implemented in the APOLLO3 version of the neutron transport solver TDT.

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.