Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions

Abstract : Let ${\cal P}=\{h_1, \ldots, h_s\}\subset \Z[Y_1, \ldots, Y_k]$, $D\geq \deg(h_i)$ for $1\leq i \leq s$, $\sigma$ bounding the bit length of the coefficients of the $h_i$'s, and $\Phi$ be a quantifier-free ${\cal P}$-formula defining a convex semi-algebraic set. We design an algorithm returning a rational point in ${\cal S}$ if and only if ${\cal S}\cap \Q\neq\emptyset$. It requires $\sigma^{\bigO(1)}D^{\bigO(k^3)}$ bit operations. If a rational point is outputted its coordinates have bit length dominated by $\sigma D^{\bigO(k^3)}$. Using this result, we obtain a procedure deciding if a polynomial $f\in \Z[X_1, \ldots, X_n]$ is a sum of squares of polynomials in $\Q[X_1, \ldots, X_n]$. Denote by $d$ the degree of $f$, $\tau$ the maximum bit length of the coefficients in $f$, $D={{n+d}\choose{n}}$ and $k\leq D(D+1)-{{n+2d}\choose{n}}$. This procedure requires $\tau^{\bigO(1)}D^{\bigO(k^3)}$ bit operations and the coefficients of the outputted polynomials have bit length dominated by $\tau D^{\bigO(k^3)}$.
Type de document :
Article dans une revue
SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2010, 20 (6), pp.2876-2889. 〈10.1137/090772459〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00419983
Contributeur : Mohab Safey El Din <>
Soumis le : jeudi 15 octobre 2009 - 19:22:30
Dernière modification le : jeudi 11 janvier 2018 - 06:20:06
Document(s) archivé(s) le : mardi 15 juin 2010 - 22:16:19

Fichiers

RR-7045.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mohab Safey El Din, Lihong Zhi. Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2010, 20 (6), pp.2876-2889. 〈10.1137/090772459〉. 〈inria-00419983〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

217