رئاسـة البـحث : Jean-Charles FAUGÈRE

تأطـير مـشـترك : SAFEY EL DIN Mohab

Regularization of Gröbner basis computations for weighted and determinantal systems, and an application to medical imagery

Polynomial system solving is a problem with numerous applications, and Gröbner bases are an important tool in this context. Previous studies have shown that systèmes arising in applications usually exhibit more structure than arbitrary systems, and that these structures can be used to make Gröbner bases computations easier. In this thesis, we consider two examples of such structures. First, we study weighted homogeneous systems, which are homogeneous if we give to each variable a specific weight when computing the degree. This structure appears naturally in many applications, including a cryptographical problem (discrete logarithm). We show how existing algorithms, which are efficient for homogeneous systems, can be adapted to a weighted setting. The complexity bounds for generic weighted homogeneous systems are divided by a factor polynomial in the product of the weights, when compared to the bounds for generic homogeneous systems with the same degree. Then we consider a real roots classification problem for varieties defined by determinants. This problem has a direct application in control theory, for contrast optimization in magnetic resonance imagery (MRI). This specific problem appears to be out of reach of previous algorithms. We show how, by adapting these algorithms to the determinantal structure of the system, the computations become practicable. As an illustration, we answer the questions from the application to contrast optimization.

إصدارات 2013-2017