Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets
| Autor: | Ivan Bannwarth, Mohab Safey El Din |
|---|---|
| Přispěvatelé: | Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-11-BS03-0011,GEOLMI,Geométrie et algèbre des inégalités matricielles linéaires avec applications en commande(2011) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Polynomial Real solutions ACM: I.: Computing Methodologies/I.1: SYMBOLIC AND ALGEBRAIC MANIPULATION/I.1.2: Algorithms Dimension of an algebraic variety Complex dimension Randomized algorithm Cylindrical algebraic decomposition Real dimension Polynomial systems Algebra Real Geometry General Terms Algorithms ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems Quantifier elimination Real algebraic geometry Theory Algebraic number Mathematics |
| Zdroj: | ISSAC'15-40th International Symposium on Symbolic and Algebraic Computation ISSAC'15-40th International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. pp.37-44, ⟨10.1145/2755996.2756670⟩ ISSAC |
| DOI: | 10.1145/2755996.2756670⟩ |
| Popis: | International audience; Let f ∈ Q[X1,. .. , Xn] be a polynomial of degree D. We consider the problem of computing the real dimension of the real algebraic set defined by f = 0. Such a problem can be reduced to quanti-fier elimination. Hence it can be tackled with Cylindrical Algebraic Decomposition within a complexity that is doubly exponential in the number of variables. More recently, denoting by d the dimension of the real algebraic set under study, deterministic algorithms running in time D O(d(n−d)) have been proposed. However, no implementation reflecting this complexity gain has been obtained and the constant in the exponent remains unspecified. We design a probabilistic algorithm which runs in time which is essentially cubic in D d(n−d). Our algorithm takes advantage of gener-icity properties of polar varieties to avoid computationally difficult steps of quantifier elimination. We also report on a first implementation. It tackles examples that are out of reach of the state-of-the-art and its practical behavior reflects the complexity gain. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|