Projet de recherche doctoral numero :8308

Description

Date depot: 11 avril 2022
Titre: Efficient linear algebra on GPUs for Gröbner bases computations
Directeur de thèse: Stef GRAILLAT (LIP6)
Encadrant : Jérémy BERTHOMIEU (LIP6)
Encadrant : Theo MARY (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie

Resumé: The main objective of this Ph.D. thesis is the design of fast Gröbner bases computation algorithms, based on high performance linear algebra algorithms, in particular exploiting GPUs, and their integration into msolve in order to tackle applications challenges such as multivariate cryptography or robotics. This global goal will be decomposed into three increasingly ambitious objectives, each of which we envision taking about one year of the Ph.D. Year 1: efficicent modular arithmetic. A first crucial goal of this Ph.D. thesis is revisiting modular arithmetic at the core of exact algorithms. Year 2: high performance linear algebra for Gröbner bases. Once the basic kernels in modular arithmetic are efficient, we will turn to their use within the Gröbner bases computation itself. The objective will be to design Gröbner bases algorithms that are both efficient for handling our matrices and dedicated to GPUs. Year 3: Gröbner bases at scale. In the final year of the Ph.D, we will aim to bring the efficient methods developed during the first two years at scale, in order to tackle very large problems whose solving will unlock new advances in critical applications.