Multifrontal Methods: Parallelism, Memory Usage and Numerical Aspects

Direct methods for the solution of sparse systems of linear equations are used in a wide range of numerical simulation applications. Such methods are based on the decomposition of the matrix into the product of triangular factors, followed by triangular solves. In comparison to iterative methods, they are known for their numerical accuracy and robustness. However, they are also characterized by a high memory consumption (especially for 3D problems) and a large amount of computations. The quality of the computed solution, the numerical functionalities and the computation time are essential parameters, while the use of material resources (number of processors and memory usage) must be carefully optimized. In this habilitation thesis, we describe some work to pursue these objectives in the context of the sparse direct solver MUMPS, developed in Toulouse, Lyon-Grenoble and Bordeaux. The approach relies on an original parallelization of the multifrontal method for distributed-memory machines, in which an asynchronous management of parallelism associated with distributed scheduling algorithms allows for dynamic datastructures and numerical pivoting. We consider task scheduling, optimization of the memory usage, and various numerical functionalities. On- going and future work aim at efficiently solving problems that are always bigger, while maintaining numerical stability and adapting our approaches to the quick evolutions of computer platforms: increase of the number of computing nodes, increase of the number of cores per node, but decrease of memory per core. In this context, software engineering and technology transfer aspects become critical in order to maintain in the long term a software package like MUMPS. This software is both necessary to our research and widely used in industry, maximizing feedback that validates our work and provides future work directions.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