Supervision : Jean-Charles FAUGÈRE

Co-supervision : 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 Publications

• 2017
  • B. Bonnard, O. Cots, J.‑Ch. Faugère, A. Jacquemard, J. Rouot, M. Safey El Din, Th. Verron : “Algebraic-geometric techniques for the feedback classification and robustness of the optimal control of a pair of Bloch equations with application to Magnetic Resonance Imaging”, (2017)
• 2016
  • Th. Verron : “Regularization of Gröbner basis computations for weighted and determinantal systems, and an application to medical imagery”, thesis, phd defence 09/26/2016, supervision Faugère, Jean-Charles, co-supervision : Safey, EL DIN Mohab (2016)
  • J.‑Ch. Faugère, M. Safey El Din, Th. Verron : “On the complexity of computing Gröbner bases for weighted homogeneous systems”, Journal of Symbolic Computation, vol. 76, pp. 107-141, (Elsevier) (2016)
  • B. Bonnard, J.‑Ch. Faugère, A. Jacquemard, M. Safey El Din, Th. Verron : “Determinantal sets, singularities and application to optimal control in medical imagery”, International symposium on symbolic and algebraic computations, Waterloo, Canada, pp. 103-110, (ACM) (2016)
• 2013
  • J.‑Ch. Faugère, M. Safey El Din, Th. Verron : “On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems”, ISSAC '13 : Proceedings of the 38^th International Symposium on Symbolic and Algebraic Computation, Boston, Maine, United States, pp. 189-196, (ACM) (2013)