PhD thesis
PhD ThesisComplexity of solving parametric polynomial systems (in french)

Date of defense : October 13, 2006 at the university of Rennes 1
Laboratory : IRMAR, Institute of Mathematical Research of Rennes.
Advisor : Dimitri Grigoriev
Members of the jury of defense : Pascal Koiran (Reporter), Bernard Mourrain (Reporter), Fabrice Rouillier (Inspector), Marie-Françoise Roy (Inspector), Eric Schost (Inspector).

Abstract : We present three algorithms in this paper: the first algorithm solves zero-dimensional parametric homogeneous polynomial systems with single exponential time in the number n of the unknowns, it decomposes the parameters space into a finite number of constructible sets and computes the finite number of solutions by parametric rational representations uniformly in each constructible set. The second algorithm factorizes absolutely multivariate parametric polynomials with single exponential time in n and in the degree upper bound d of the factorized polynomials. The third algorithm decomposes the algebraic varieties defined by parametric polynomial systems of positive dimensions into absolutely irreducible components uniformly on the values of the parameters. The complexity bound of this algorithm is double-exponential in n. On the other hand, the complexity lower bound of the problem of resolution of parametric polynomial systems is double-exponential in n.

Résumé : On présente trois algorithmes dans cette thèse: Le premier algorithme résout de systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnues, cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini des solutions par de représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument de polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d des degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par de systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution des systèmes algébriques paramétrés est doublement exponentielle en n.