Méthodes de Krylov pour l'algèbre linéaire et implémentation polymorphe

Ce projet de recherche se situe à la frontière entre les mathématiques appliquées et l’informatique théorique. Il dépend du domaine de l’algèbre linéaire numérique et se focalise sur le développement d’algorithmes de résolution de systèmes linéaires. Dans notre cadre d’étude, les algorithmes de résolution sont itératifs, c’est-à-dire qu’ils génèrent une suite de solutions approximatives. Ces itérés sont construits de telle sorte qu’ils résident dans un espace de Krylov. Un espace de Krylov est généré par le produit répété d’une matrice à un vecteur initial. Un exemple d’espace de Krylov est l’ensemble des combinaisons linéaires de b, Ab et A2b. Les algorithmes ayant cette propriété sont considérés comme des méthodes de Krylov. Les recherches résumées dans ce document se décomposent en deux composantes. La première est théorique et englobe le développement d’un nouveau processus de Krylov appelé Ortho-gonal Hessenberg Reduction ainsi que huit nouvelles méthodes de Krylov (BiLQ, BiLQR, TriLQR, TriCG, TriMR, Gpmr, MinAres, cAr), mieux adaptées aux caractéristiques de certains systèmes linéaires. La seconde, axée sur l’aspect logiciel, concerne l’implémentation générique et modulaire de ces nouveaux algorithmes. Ces implémentations doivent s’adapter à divers domaines d’applications, incluant différents modes de stockage et de modélisation sur ordinateur. Un système linéaire peut être stocké avec différentes précisions machine, telles que simple, double ou quadruple précision, être résolu sur CPU ou GPU, ou encore être représenté dans différents formats de matrices, qu’elles soient creuses ou denses. Ces aspects soulignent la nécessité d’une implémentation polymorphe pour s’adapter à ces multiples configurations. Une implémentation polymorphe se réfère à la capacité d’un code informatique à traiter des paramètres de manière flexible, en leur permettant d’adopter différentes formes ou types en fonction du contexte. Ces travaux sont rassemblés dans la bibliothèque numérique Krylov.jl, implémentée dans le langage de programmation Julia. Ce langage de programmation est adéquat au projet en rai-son de sa fonctionnalité de dispatch multiple ; un mécanisme informatique permettant d’écrire une fonction une seule fois, et voir celle-ci compilée à la volée pour différentes configurations suivant le type des arguments. Krylov.jl s’est illustré pour résoudre des systèmes linéaires creux sur les deux supercalculateurs les plus puissants du monde, Frontier du laboratoire national d’Oak Ridge et Aurora du laboratoire national d’Argonne. Il offre la portabilité nécessaire aux nouvelles architectures des cartes graphiques AMD et Intel, respectivement présentes dans Frontier et Aurora.

Abstract

This research project lies at the intersection of applied mathematics and computer science. It is based on numerical linear algebra and focuses on the development of algorithms for solving linear systems. In our framework, the algorithms are iterative, meaning that they generate a sequence of approximate solutions. These iterates are built such that they lie in a Krylov subspace. A Krylov subspace is generated by the repeated product of a matrix to an initial vector. An example of a Krylov space is the set of linear combinations of b, Ab, and A2b. The algorithms with this property are Krylov methods. The research summarized in this document consists of two components. The first is theoretical and encompasses the development of a new Krylov process called Orthogonal Hessenberg Reduction as well as eight new Krylov methods (BiLQ, BiLQR, TriLQR, TriCG, TriMR, Gpmr, MinAres, cAr), better suited to the characteristics of certain linear systems. The second, focusing on the software aspect, concerns the generic and mod-ular implementation of these new algorithms. These implementations must adapt to various application domains, including different modeling and computer storage. A linear system may be stored with different machine precisions, such as single, double, or quadruple precision, solved on CPU or GPU, or represented in different matrix formats, whether sparse or dense. These aspects highlight the need for a polymorphic implementation to adapt to these multiple configurations. A polymorphic implementation refers to the ability of a com-puter code to handle parameters flexibly, allowing them to take on different forms or types depending on the context. These works are consolidated in the numerical library Krylov.jl, implemented in the Julia programming language. This programming language is suitable for the project due to its multiple dispatch feature; a mechanism that allows writing a function only once and having it compiled on-the-fly for different configurations depending on the types of the arguments. Krylov.jl has showcased its capabilities in solving sparse linear systems on world’s two most powerful supercomputers, Frontier at the Oak Ridge National Laboratory and Aurora at the Argonne National Laboratory. It provides portability to the new architectures of AMD and Intel graphics cards, present respectively in Frontier and Aurora.