Littérature scientifique sur le sujet « Solveurs linéaires directs »

L'évaluation de l'intégrité des structures est un aspect important des exigences de sécurité dans les applications industrielles de pointe, comme par exemple l’aéronautique et le nucléaire. Le Structural Health Monitoring (SHM) propose d'utiliser des capteurs et des unités de traitement du signal in situ pour surveiller l’état d’une structure. Les ondes ultrasonores guidées constituent l'un des moyens de mettre en oeuvre les systèmes SHM. Les performances d’une solution SHM sont affectées par les conditions opérationnelles et en particulier les contraintes mécaniques. Un exemple typique est celui des charges opérationnelles induisant de grandes déformations et par conséquent des contraintes internes qui entraînent des changements dans la propagation des ondes. Il est donc important que la modélisation de la propagation des ondes prenne en compte ces phénomènes pour l’interprétation des signaux, la démonstration de performance et la conception des systèmes. L'objectif de notre travail est de proposer un modèle, et les méthodes numériques correspondantes, pour la propagation d’ondes élastiques dans un milieu précontraint. Comme les structures considérées sont généralement minces, nous utilisons une formulation de coque pour la mécanique non linéaire pour résoudre le problème quasi-statique, représentant les effets du chargement de la structure. Le déplacement calculé est ensuite transmis à un solveur éléments finis spectraux (SFEM) pour résoudre le problème élastodynamique linéarisé dans le domaine temporel. Au-delà de la modélisation directe nous visons à utiliser ces outils dans les boucles d'inversion pour la reconstruction de la contrainte mécanique à partir de mesures ultrasonores. Le modèle s’applique de la même façon à des configurations SHM ou à des configurations d’END et il a pour vocation d’enrichir la plateforme CIVA.

Cette these traite des problemes du calcul haute performance et plus specifiquement du calcul parallele scientifique pour des applications irregulieres en vraie grandeur. Dans une premiere partie, nous presentons une contribution aux optimisations du recouvrement calcul/communication sur des architectures paralleles a memoire distribuee, avec en particulier le calcul du grain optimal et de la taille optimale des paquets a communiquer. Nous nous sommes egalement interesses au calcul de la granularite maximisant le recouvrement calcul/communication pour l'algorithme de factorisation de cholesky pour des matrices pleines en exploitant l'irregularite due a la symetrie de cette matrice. Ces travaux ont debouche sur le developpement d'une bibliotheque portable integrant ces mecanismes de decoupage des messages. La seconde partie decrit un ordonnancement statique des calculs pour le probleme de la resolution parallele directe de grands systemes lineaires creux, conduisant au masquage quasi-total des communications. La mise en uvre de ces travaux nous a conduit a implementer un solveur direct parallele pour la factorisation de cholesky par blocs, avec des distribution 1d et / ou 2d, integrant l'approche fan-in et presentant des performances qui se comparent tres favorablement aux meilleurs solveurs paralleles directs actuels.

La résolution de systèmes linéaires creux est critique dans de nombreux domaines de la simulation numérique. Beaucoup d'applications, notamment industrielles, utilisent des méthodes directes en raison de leur précision et de leur robustesse. La qualité du résultat, les fonctionnalités numériques, ainsi que le temps de calcul sont critiques pour les applications. Par ailleurs, les ressources matérielles (nombre de processeurs, mémoire) doivent être utilisées de manière optimale. Dans cette habilitation, nous décrivons des travaux poursuivant ces objectifs dans le cadre de la plate-forme logicielle MUMPS, développée à Toulouse, Lyon-Grenoble et Bordeaux depuis une quinzaine d'années. Le cœur de l'approche repose sur une parallélisation originale de la méthode multifrontale : une gestion asynchrone du parallélisme, associée à des ordonnanceurs distribués, permet de traiter des structures de données dynamiques et autorise ainsi le pivotage numérique. Nous nous intéressons à l'ordonnancement des tâches, à l'optimisation de la mémoire et à différentes fonctionnalités numériques. Les travaux en cours et les objectifs futurs visent à résoudre efficacement des problèmes de plus en plus gros, sans perte sur les aspects numériques, et tout en adaptant nos approches aux évolutions rapides des calculateurs. Dans ce contexte, les aspects génie logiciel et transfert deviennent critiques afin de maintenir sur le long terme une plate-forme logicielle comme MUMPS. Cette plate-forme est à la fois nécessaire à nos travaux de recherche et utilisée en production ; elle maximise ainsi les retours applicatifs qui valident nos travaux et permettent d'orienter nos recherches futures.

Pour résoudre des systèmes linéaires creux de grande taille, on peut vouloir utiliser des méthodes directes, numériquement robustes, mais coûteuses en termes d'utilisation de la mémoire et de temps de résolution. C'est le cas de la méthode multifrontale, notamment implémentée par le solveur MUMPS. L’une des fonctionnalités disponibles dans ce solveur est l’utilisation de la compression Block Low-Rank (BLR), qui améliore les performances. L'objectif de cette thèse est d'explorer plusieurs pistes d'amélioration de cette compression BLR, de façon à améliorer les performances de la méthode multifrontale. En particulier, nous proposons une variante de la compression BLR utilisant simultanément plusieurs formats de nombres à virgule flottante (précision mixte). Notre démarche, basée sur une analyse d'erreur, permet dans un premier temps de réduire la complexité d'une factorisation LU de matrice dense, sans pour autant impacter l'erreur commise de façon significative. Dans un second temps, nous adaptons ces algorithmes à la méthode multifrontale. Une première implémentation utilise notre compression BLR en précision mixte comme format de stockage, et permet ainsi de réduire la consommation mémoire de MUMPS. Une seconde implémentation permet de combiner ces gains en mémoire avec des gains en temps lors de la phase de résolution de systèmes triangulaires, grâce à des calculs effectués en précision faible. Cependant, nous remarquons que cette étape n'est pas aussi performante que prévu en BLR, dans le cas d'un système linéaire à plusieurs seconds membres. Pour y remédier, nous proposons de nouvelles variantes BLR de la résolution de systèmes triangulaires, dans laquelle la localité mémoire a été améliorée. Nous justifions l'intérêt de cette approche grâce à une analyse de volume de communication. Nous implémentons nos algorithmes dans un prototype simplifié, puis dans MUMPS, et nous obtenons des gains en temps dans les deux cas
In order to solve large sparse linear systems, one may want to use a direct method, numerically robust but rather costly, both in terms of memory consumption and computation time. The multifrontal method belong to this class algorithms, and one of its high-performance parallel implementation is the solver MUMPS. One of the functionalities of MUMPS is the use of Block Low-Rank (BLR) matrix compression, that improves its performance. In this thesis, we present several new techniques aiming at further improving the performance of dense and sparse direct solvers, on top of using a BLR compression. In particular, we propose a new variant of BLR compression in which several floating-point formats are used simultaneously (mixed precision). Our approach is based on an error analysis, and it first allows to reduce the estimated cost of a LU factorization of a dense matrix, without having a significant impact on the error. Second, we adapt these algorithms to the multifrontal method. A first implementation uses our mixed-precision BLR compression as a storage format only, thus allowing to reduce the memory footprint of MUMPS. A second implementation allows to combine these memory gains with time reductions in the triangular solution phase, by switching computations to low precision. However, we notice performance issues related to BLR for this phase, in case the system has many right-hand sides. Therefore, we propose new BLR variants of triangular solution that improve the data locality and reduce data movements, as highlighted by a communication volume analysis. We implement our algorithms within a simplified prototype and within solver MUMPS. In both cases, we obtain time gains

Cette thèse se concentre sur la résolution de systèmes linéaires creux dans le contexte d’applications massivement parallèles. Ce type de problèmes s’exprime sous la forme AX=B, où A est une matrice creuse d’ordre n x n, i.e. qui possède un nombre d’entrées nulles suffisamment élevé pour pouvoir être exploité, et B et X sont respectivement la matrice de seconds membres et la matrice de solution de taille n x nrhs. Cette résolution par des méthodes dites directes est effectuée grâce à une étape de factorisation qui réduit A en deux matrices triangulaires inférieure et supérieure L et U, suivie de deux résolutions triangulaires pour calculer la solution.Nous nous intéressons à ces résolutions avec une attention particulière apportée à la première, LY=B. Dans beaucoup d’applications, B possède un grand nombre de colonnes (nrhs >> 1) transformant la phase de résolution en un goulot d’étranglement. Elle possède souvent aussi une structure creuse, donnant l’opportunité de réduire la complexité de cette étape.Cette étude aborde sous des angles complémentaires la résolution triangulaire de systèmes linéaires avec seconds membres multiples et creux. Nous étudions dans un premier temps la complexité asymptotique de cette étape dans différents contextes (2D, 3D, facteurs compressés ou non). Nous considérons ensuite l’exploitation de cette structure et présentons de nouvelles approches s’appuyant sur une modélisation du problème par des graphes qui permettent d’atteindre efficacement le nombre minimal d’opérations. Enfin, nous donnons une interprétation concrète de son exploitation sur une application d’électromagnétisme pour la géophysique. Nous adaptons aussi des algorithmes parallèles aux spécificités de la phase de résolution.Nous concluons en combinant l'ensemble des résultats précédents et en discutant des perspectives de ce travail
We consider direct methods to solve sparse linear systems AX = B, where A is a sparse matrix of size n x n with a symmetric structure and X and B are respectively the solution and right-hand side matrices of size n x nrhs. A is usually factorized and decomposed in the form LU, where L and U are respectively a lower and an upper triangular matrix. Then, the solve phase is applied through two triangular resolutions, named respectively the forward and backward substitutions.For some applications, the very large number of right-hand sides (RHS) in B, nrhs >> 1, makes the solve phase the computational bottleneck. However, B is often sparse and its structure exhibits specific characteristics that may be efficiently exploited to reduce this cost. We propose in this thesis to study the impact of the exploitation of this structural sparsity during the solve phase going through its theoretical aspects down to its actual implications on real-life applications.First, we investigate the asymptotic complexity, in the big-O sense, of the forward substitution when exploiting the RHS sparsity in order to assess its efficiency when increasing the problem size. In particular, we study on 2D and 3D regular problems the asymptotic complexity both for traditional full-rank unstructured solvers and for the case when low-rank approximation is exploited. Next, we extend state-of-the-art algorithms on the exploitation of RHS sparsity, and also propose an original approach converging toward the optimal number of operations while preserving performance. Finally, we show the impact of the exploitation of sparsity in a real-life electromagnetism application in geophysics that requires the solution of sparse systems of linear equations with a large number of sparse right-hand sides. We also adapt the parallel algorithms that were designed for the factorization to solve-oriented algorithms.We validate and combine the previous improvements using the parallel solver MUMPS, conclude on the contributions of this thesis and give some perspectives

La résolution de systèmes linéaires creux est un problème qui apparaît dans de nombreuses applications scientifiques, et les solveurs creux sont une étape coûteuse pour ces applications ainsi que pour des solveurs plus avancés comme les solveurs hybrides direct-itératif. Pour ces raisons, optimiser la performance de ces solveurs pour les architectures modernes est un problème critique. Cependant, les contraintes mémoire et le temps de résolution limitent l’utilisation de ce type de solveur pour des problèmes de très grande taille. Pour les approches concurrentes, par exemple les méthodes itératives, des préconditionneurs garantissant une bonne convergence pour un large ensemble de problèmes sont toujours inexistants. Dans la première partie de cette thèse, nous présentons deux approches exploitant la compression Block Low-Rank (BLR) pour réduire la consommation mémoire et/ou le temps de résolution d’un solveur creux. Ce format de compression à plat, sans hiérarchie, permet de tirer profit du caractère low-rank des blocs apparaissant dans la factorisation de systèmes linéaires creux. La solution proposée peut être utilisée soit en tant que solveur direct avec une précision réduite, soit comme un préconditionneur très robuste. La première approche, appelée Minimal Memory, illustre le meilleur gain mémoire atteignable avec la compression BLR, alors que la seconde approche, appelée Just-In-Time, est dédiée à la réduction du nombre d’opérations, et donc du temps de résolution. Dans la seconde partie, nous présentons une stratégie de reordering qui augmente la granularité des blocs pour tirer davantage profit de la localité dans l’utilisation d’architectures multi-coeurs et pour fournir de tâches plus volumineuses aux GPUs. Cette stratégie s’appuie sur la factorisation symbolique par blocs pour raffiner la numérotation produite par des outils de partitionnement comme Metis ou Scotch, et ne modifie pas le nombre d’opérations nécessaires à la résolution du problème. A partir de cette approche, nous proposons dans la troisième partie de ce manuscrit une technique de clustering low-rank qui a pour objectif de former des clusters d’inconnues au sein d’un séparateur. Nous démontrons notamment les intérêts d’une telle approche par rapport aux techniques de clustering classiquement utilisées. Ces deux stratégies ont été développées pour le format à plat BLR, mais sont également une première étape pour le passage à un format hiérarchique. Dans la dernière partie de cette thèse, nous nous intéressons à une modification de la technique de dissection emboîtée afin d’aligner les séparateurs par rapport à leur père pour obtenir des structures de données plus régulières
Solving sparse linear systems is a problem that arises in many scientific applications, and sparse direct solvers are a time consuming and key kernel for those applications and for more advanced solvers such as hybrid direct-iterative solvers. For those reasons, optimizing their performance on modern architectures is critical. However, memory requirements and time-to-solution limit the use of direct methods for very large matrices. For other approaches, such as iterative methods, general black-box preconditioners that can ensure fast convergence for a wide range of problems are still missing. In the first part of this thesis, we present two approaches using a Block Low-Rank (BLR) compression technique to reduce the memory footprint and/or the time-to-solution of a supernodal sparse direct solver. This flat, non-hierarchical, compression method allows to take advantage of the low-rank property of the blocks appearing during the factorization of sparse linear systems. The proposed solver can be used either as a direct solver at a lower precision or as a very robust preconditioner. The first approach, called Minimal Memory, illustrates the maximum memory gain that can be obtained with the BLR compression method, while the second approach, called Just-In-Time, mainly focuses on reducing the computational complexity and thus the time-to-solution. In the second part, we present a reordering strategy that increases the block granularity to better take advantage of the locality for multicores and provide larger tasks to GPUs. This strategy relies on the block-symbolic factorization to refine the ordering produced by tools such as Metis or Scotch, but it does not impact the number of operations required to solve the problem. From this approach, we propose in the third part of this manuscript a new low-rank clustering technique that is designed to cluster unknowns within a separator to obtain the BLR partition, and demonstrate its assets with respect to widely used clustering strategies. Both reordering and clustering where designed for the flat BLR representation but are also a first step to move to hierarchical formats. We investigate in the last part of this thesis a modified nested dissection strategy that aligns separators with respect to their father to obtain more regular data structure

Cette thèse présente une méthode parallèle de résolution de systèmes linéaires creux basée sur un algorithme multigrille géométrique. Les estimations de la solution sont calculées par méthode directe sur le niveau grossier ou par méthode itérative de type splitting sur les maillages raffinés; des opérateurs inter-grilles sont définis pour interpoler les solutions approximatives entre les différents niveaux de raffinements. Ce solveur est utilisé dans le cadre de simulations électromagnétiques en 3D (équations de Maxwell en régime harmonique discrétisées par éléments finis de Nédélec de premier ordre) en tant que méthode stationnaire ou comme préconditionneur d’une méthode de Krylov (GMRES)
Multigrid algorithm. The system is solved thanks to a direct method on the coarse mesh anditerative splitting method on refined meshes; inter-grid operators are defined to interpolate theapproximate solutions on the different refinement levels. Applied to 3D electromagnetic simulations(Nédélec first order finite element approximation of time harmonic Maxwell equations) thissolver is used either as a stationary method or as a preconditioner for a Krylov subspace method(GMRES)

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels.

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels
This thesis presents a parallel resolution method for sparse linear systems which combines effectively techniques of direct and iterative solvers using a Schur complement approach. A domain decomposition is built ; the interiors of the subdomains are eliminated by a direct method in order to use an iterative method only on the interface unknowns. The system on the interface (Schur complement) is solved thanks to an iterative method preconditioned by a global incomplete factorization. A special ordering on the Schur complement allows to build a scalable preconditioner. Algorithms minimizing the memory peak that appears during the construction of the preconditioner are presented. The memory is balanced thanks to a multiple domains per processors parallelization scheme. The methods are implemented in the HIPS solver and parallel experimental results are presented on large industrial test cases

La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques de calcul intensif. La résolution performante de ces systèmes passe par la conception, le développement et l'utilisation d'algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l'évaluation d'une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. La stratégie de développement est axée sur l'utilisation des machines massivement parallèles de plusieurs milliers de processeurs. L'étude systématique de l'extensibilité et l'efficacité parallèle de différents préconditionneurs algébrique est réalisée aussi bien d'un point de vue informatique que numérique. On a comparé leurs performances sur des systèmes de plusieurs millions ou dizaines de millions d'inconnues pour des problèmes réels 3D
Large-scale scientific applications and industrial simulations are nowadays fully integrated in many engineering areas. They involve the solution of large sparse linear systems. The use of large high performance computers is mandatory to solve these problems. The main topic of this research work was the study of a numerical technique that had attractive features for an efficient solution of large scale linear systems on large massively parallel platforms. The goal is to develop a high performance hybrid direct/iterative approach for solving large 3D problems. We focus specifically on the associated domain decomposition techniques for the parallel solution of large linear systems. We have investigated several algebraic preconditioning techniques, discussed their numerical behaviors, their parallel implementations and scalabilities. We have compared their performances on a set of 3D grand challenge problems

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures
New supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures