Complexity of finding irreducible components of a semialgebraic set
Let \(W \subset \mathbb{R}^ n\) be a semialgebraic set determined by a Boolean combination of \(k\) atomic subformulas of the form \(f > 0\) or \(f = 0\), where the polynomials \(f \in \mathbb{Z} [X_ 1, \dots, X_ n]\), the degrees \(\deg_{X_ 1, \dots, X_ n} (f) < d\), and the maxima of bit lengths of coefficients \(l(f) < M\) for \(d\), \(M \in \mathbb{N}\). The author proposes an algorithm for producing the complexification, the Zariski closure and for finding all irreducible components of \(W\). An upper bound for the running time is \(M^{0(1)} (kd)^{n^{0(1)}}\). The procedure is applied to computing a Whitney system for a semialgebraic set and the real radical of a polynomial ideal.
- Complexity of computing the local dimension of a semialgebraic set
- Description of the connected components of a semialgebraic set in single exponential time
- The complexity of irredundant sets parameterized by size
- Generators for the \(C^m\)-closures of ideals
- Computing real radicals and S-radicals of polynomial systems
- Ax-Lindemann for \(\mathcal{A}_g\)
- A semi-algebraic version of Zarankiewicz's problem
- scientific article; zbMATH DE number 21309 (Why is no real title available?)
- scientific article; zbMATH DE number 1254270 (Why is no real title available?)
- scientific article; zbMATH DE number 1262423 (Why is no real title available?)
- The André-Oort conjecture for the moduli space of abelian surfaces
- ON THE IRREDUCIBLE COMPONENTS OF A SEMIALGEBRAIC SET
- Finding connected components of a semialgebraic set in subexponential time
- Computing real radicals by moment optimization
- Intersection queries for flat semi-algebraic objects in three dimensions and related problems
- Intersection searching amid tetrahedra in four dimensions
This page was built for publication: Complexity of finding irreducible components of a semialgebraic set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346599)
