Contributions to relaxed algorithms and polynomial system solving

Contributions à l'algorithmique détendue et à la résolution des systèmes polynomiaux

Romain Lebreton (1)

1 MAX

This PhD thesis is mostly devoted to the computation of p-adic lifting by relaxed algorithms. In a first part, we introduce relaxed algorithms and their application to the computation of recursive p-adics. In order to use this framework for the p-adic lifting of various systems of equations, we have to transform the given implicit equations into recursive equations. The case of systems of linear equations, possibly differential, is treated in the second part. This third part contains the lifting of resolutions of polynomial systems. In any cases, these new relaxed algorithms are compared, both in theory and practice, to existing algorithms. In the fourth part, we focus on the universal decomposition algebra. We present a fast algorithm which computes an adequate representation of this algebra and use it to compute efficiently with the elements of this algebra. Finally, we show in the appendix that finding fundamental invariants of polynomial invariants algebras under a finite group can be done directly modulo p, hence making their computation easier.

Cette thèse est en majeure partie dédiée au calcul rapide de remontée p-adique par des algorithmes détendus. Dans une première partie, nous présentons le cadre général des algorithmes détendus et de leur application au calcul de p-adiques récursifs. Pour appliquer ce cadre à la remontée p-adique de divers systèmes d'équations, il reste à transformer ces équations implicites en équations récursives. Ainsi, la seconde partie traite des systèmes d'équations linéaires, éventuellement différentiels. La remontée de résolutions de systèmes polynomiaux se trouve en troisième partie. Dans tous les cas, les nouveaux algorithmes détendus sont comparés, en théorie comme en pratique, aux algorithmes existants. En quatrième partie, nous étudions l'algèbre de décomposition universelle d'un polynôme. Nous développons un algorithme rapide pour calculer une représentation adéquate de cette algèbre et l'utilisons pour manipuler efficacement les éléments de l'algèbre. Finalement, nous montrons en annexe que la recherche d'invariants fondamentaux d'algèbres d'invariants sous un groupe fini peut se faire directement modulo p, facilitant ainsi leur calcul.

Mots clés: Relaxed algorithm; on-line algorithm; polynomial system solving; p-adic lifting

Mots clés: Algorithme détendu; résolution de systèmes polynomiaux; remontée p-adique

Domaines: Calcul formel [cs.SC]

Romain Lebreton. Contributions à l'algorithmique détendue et à la résolution des systèmes polynomiaux. Calcul formel [cs.SC]. Ecole Polytechnique X, 2012. Français. ⟨NNT : ⟩. ⟨tel-00780618⟩