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

2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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)}$.
Keywords :
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〉
Domaine :

Littérature citée [21 références]

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)

### 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〉

### Métriques

Consultations de la notice

## 229

Téléchargements de fichiers