Computing rational solutions of linear matrix inequalities

Qingdong Guo 1 Mohab Safey El Din 2 Lihong Zhi 1
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Consider a $(D\times D)$ symmetric matrix $\sfA$ whose entries are linear forms in $\Q[X_1, \ldots, X_k]$ with coefficients of bit size $\leq \tau$. We provide an algorithm which decides the existence of rational solutions to the linear matrix inequality $\sfA\succeq 0$ and outputs such a rational solution if it exists. This problem is of first importance: it can be used to compute algebraic certificates of positivity for multivariate polynomials. Our algorithm runs within $(k\tau)^{O(1)}2^{O(\min(k, D)D^2)}D^{O(D^2)}$ bit operations; the bit size of the output solution is dominated by $\tau^{O(1)}2^{O(\min(k, D)D^2)}$. These results are obtained by designing algorithmic variants of constructions introduced by Klep and Schweighofer. This leads to the best complexity bounds for deciding the existence of sums of squares with rational coefficients of a given polynomial. We have implemented the algorithm; it has been able to tackle Scheiderer's example of a multivariate polynomial that is a sum of squares over the reals but not over the rationals; providing the first computer validation of this counter-example to Sturmfels' conjecture.
Type de document :
Communication dans un congrès
ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00815174
Contributeur : Mohab Safey El Din <>
Soumis le : jeudi 18 avril 2013 - 11:52:00
Dernière modification le : lundi 29 mai 2017 - 14:22:49
Document(s) archivé(s) le : lundi 3 avril 2017 - 06:57:43

Fichier

rational-lmi-6.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00815174, version 1

Collections

Citation

Qingdong Guo, Mohab Safey El Din, Lihong Zhi. Computing rational solutions of linear matrix inequalities. ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. 2013. <hal-00815174>

Partager

Métriques

Consultations de
la notice

212

Téléchargements du document

158