Complexity of Resolution of Parametric Systems of Polynomial Equations and Inequations

Guillaume Moroz 1
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Consider a system of n polynomial equations and r polynomial inequations in n indeterminates of degree bounded by d with coefficients in a polynomial ring of s parameters with rational coefficients of bit-size at most $\sigma$. From the real viewpoint, solving such a system often means describing some semi-algebraic sets in the parameter space over which the number of real solutions of the considered parametric system is constant. Following the works of Lazard and Rouillier, this can be done by the computation of a discriminant variety. In this report we focus on the case where for a generic specialization of the parameters the system of equations generates a radical zero-dimensional ideal, which is usual in the applications. In this case, we provide a deterministic method computing the minimal discriminant variety reducing the problem to a problem of elimination. Moreover, we prove that the degree of the computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and that the complexity of our method is $\sigma^{\mathcal{O}(1)} D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine.
Type de document :
[Research Report] RR-5929, INRIA. 2006
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 8 juin 2006 - 17:11:30
Dernière modification le : jeudi 11 janvier 2018 - 06:20:06
Document(s) archivé(s) le : lundi 20 septembre 2010 - 15:41:10




Guillaume Moroz. Complexity of Resolution of Parametric Systems of Polynomial Equations and Inequations. [Research Report] RR-5929, INRIA. 2006. 〈inria-00078795v2〉



Consultations de la notice


Téléchargements de fichiers