La résolution de systèmes polynomiaux est un problème aux multiples applications, et les bases de Gröbner sont un outil important dans ce cadre. Il est connu que de nombreux systèmes issus d'applications présentent une structure supplémentaire par rapport à des systèmes arbitraires, et que ces structures peuvent souvent être exploitées pour faciliter le calcul de bases de Gröbner.Dans cette thèse, on s'intéresse à deux exemples de telles structures, pour différentes applications. Tout d'abord, on étudie les systèmes homogènes avec poids, qui sont homogènes si on calcule le degré en affectant un poids à chaque variable. Cette structure apparaît naturellement dans de nombreuses applications, dont un problème de cryptographie (logarithme discret). On montre comment les algorithmes existants, efficaces pour les polynômes homogènes, peuvent être adaptés au cas avec poids, avec des bornes de complexité générique divisées par un facteur polynomial en le produit des poids.Par ailleurs, on étudie un problème de classification de racines réelles pour des variétés définies par des déterminants. Ce problème a une application directe en théorie du contrôle, pour l'optimisation de contraste de l'imagerie à résonance magnétique. Ce système particulier s'avère insoluble avec les stratégies générales pour la classification. On montre comment ces stratégies peuvent tirer profit de la structure déterminantielle du système, et on illustre ce procédé en apportant des réponses aux questions posées par le problème d'optimisation de contraste. / 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 computing Gröbner bases 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 an arbitrary 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, and generically, we show that their complexity bounds can be divided by a factor polynomial in the product of the weights.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. This specific system appears to be out of reach of existing algorithms. We show how these algorithms can benefit from the determinantal structure of the system, and as an illustration, we answer the questions from the application to contrast optimization.
| Identifer | oai:union.ndltd.org:theses.fr/2016PA066355 |
| Date | 26 September 2016 |
| Creators | Verron, Thibaut |
| Contributors | Paris 6, Faugère, Jean-Charles, Safey El Din, Mohab |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0028 seconds