Critical Point Methods and Effective Real Algebraic Geometry: New Results and Trends

Mohab Safey El Din 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Critical point methods are at the core of the interplay between polynomial optimization and polynomial system solving over the reals. These methods are used in algorithms for solving various problems such as deciding the existence of real solutions of polynomial systems, performing one-block real quantifier elimination, computing the real dimension of the solution set, etc. The input consists of $s$ polynomials in $n$ variables of degree at most $D$. Usually, the complexity of the algorithms is $(s\, D)^{O(n^\alpha)}$ where $\alpha$ is a constant. In the past decade, tremendous efforts have been deployed to improve the exponents in the complexity bounds. This led to efficient implementations and new geometric procedures for solving polynomial systems over the reals that exploit properties of critical points. In this talk, we present an overview of these techniques and their impact on practical algorithms. Also, we show how we can tune them to exploit algebraic and geometric structures in two fundamental problems. The first one is real root finding of determinants of $n$-variate linear matrices of size $k\times k$. We introduce an algorithm whose complexity is polynomial in ${{n+k}\choose{k}}$ (joint work with S. Naldi and D. Henrion). This improves the previously known $k^{O(n)}$ bound. The second one is about computing the real dimension of a semi-algebraic set. We present a probabilistic algorithm with complexity $(s\, D)^{O(n)}$, that improves the long-standing $(s\, D)^{O(n^2)}$ bound obtained by Koi\-ran (joint work with E. Tsigaridas).
Type de document :
Communication dans un congrès
Manuel Kauers. ISSAC 2013 - 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. pp.5-6, 2013, 〈10.1145/2465506.2465928〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00922718
Contributeur : Mohab Safey El Din <>
Soumis le : lundi 30 décembre 2013 - 09:40:56
Dernière modification le : lundi 29 mai 2017 - 14:21:41
Document(s) archivé(s) le : dimanche 30 mars 2014 - 22:07:09

Fichier

abstract-safeyeldin.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mohab Safey El Din. Critical Point Methods and Effective Real Algebraic Geometry: New Results and Trends. Manuel Kauers. ISSAC 2013 - 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. pp.5-6, 2013, 〈10.1145/2465506.2465928〉. 〈hal-00922718〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

351