Complexity of solving parametric polynomial systems

A. Ayad

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XIX, Tome 387 (2011), pp. 5-52

Résumé

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 dimension into absolutely irreducible components uniformly in 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$.