Scalability of parallel sparse direct solvers: methods, memory and performance

The fast and accurate solution of large size sparse systems of linear equations is at the heart of numerical applications from a very broad range of domains including structural mechanics, fluid dynamics, geophysics, medical imaging, chemistry. Among the most commonly used techniques, direct methods, based on the factorization of the system matrix, are generally appreciated for their numerical robustness and ease of use. These advantages, however, come at the price of a considerable operations count and memory footprint. The work presented in this thesis is concerned with improving the scalability of sparse direct solvers, intended as the ability to solve problems of larger and larger size. More precisely, our work aims at developing solvers which are scalable in performance, memory consumption and complexity. We address performance scalability, that is the ability to reduce the execution time as more computational resources are available, introducing algorithms that improve parallelism by reducing communications and synchronizations. We discuss the use of novel parallel programming paradigms and tools to achieve their implementation in an efficient and portable way on modern, heterogeneous supercomputers. We present methods that make sparse direct solvers memory-scalable, that is, capable of taking advantage of parallelism without increasing the overall memory footprint. Finally we show how it is possible to use data sparsity to achieve an asymptotic reduction of the cost of such methods. The presented algorithms have been implemented in the freely distributed MUMPS and qr_mumps solver packages and their effectiveness assessed on reallife problems from academic and industrial applications.La solution rapide et précise de systèmes linéaires creux de grande taille est au coeur de nombreuses applications numériques issues d’une gamme très large de domaines incluant la mécanique de structure, la dynamique des fluides, la géophysique, l’imagerie médicale, la chimie. Parmi les techniques les plus couramment utilisées pour la résolution de tels problèmes, les méthodes directes, basées sur la factorisation de la matrice du système, sont généralement appréciées pour leur robustesse numérique et facilité d’utilisation. Cependant, ces méthodes induisent une complexité, en termes d’opérations et de consommation de mémoire, très élevée. Les travaux présentés dans cette thèse se concentrent sur l’amélioration de la scalabilité des méthodes creuses directes, définie comme la capacité de traiter des problèmes de taille de plus en plus importante. Nous introduisons des algorithmes capables d’atteindre un meilleur degré de parallélisme en réduisant les communications et synchronisations afin d’améliorer la scalabilité des performances, à savoir, la capacité de réduire le temps d’exécution lorsque les ressources de calcul disponibles augmentent. Nous nous intéressons à l’utilisation de nouveaux paradigmes et outils de programmation parallèle permettant une implémentation de ces algorithmes efficace et portable sur des supercalculateurs hétérogènes. Nous adressons la scalabilité en mémoire à l’aide de méthodes d’ordonnancement permettant de tirer profit du parallélisme sans augmenterla consommation de mémoire. Finalement, nous démontrons comment il est possible de réduire la complexité des méthodes creuses directes, en termes de nombre d’opérations et taille mémoire, grâce à l’utilisation de techniques d’approximation de rang faible. Les méthodes présentées, dont l’efficacité a été vérifiée sur des problèmes issus d’applications réelles, ont été implantées dans les plateformes logicielles MUMPS et qr_mumps distribuées sous licence libre