Polar varieties, real equation solving, and data structures: the hypersurface case
From MaRDI portal
Publication:1361872
DOI10.1006/JCOM.1997.0432zbMATH Open0872.68066arXivalg-geom/9609004OpenAlexW2134386365MaRDI QIDQ1361872FDOQ1361872
Marc Giusti, Bernd Bank, Joos Heintz, Guy Merlin Mbakop
Publication date: 28 July 1997
Published in: Journal of Complexity (Search for Journal in Brave)
Abstract: In this paper we apply for the first time a new method for multivariate equation solving which was developed in cite{gh1}, cite{gh2}, cite{gh3} for complex root determination to the {em real} case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm of cite{gh1}, cite{gh2}, cite{gh3} yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem--adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in non-uniform sequential time that is {em polynomial} in the length of the input (given in straight--line program representation) and an adequately defined {em geometric degree of the equation system}. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined {em real (or complex) degree} of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.
Full work available at URL: https://arxiv.org/abs/alg-geom/9609004
Recommendations
- Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case
- scientific article; zbMATH DE number 1552220
- Polar, bipolar and copolar varieties: real solving of algebraic varieties with intrinsic complexity
- Generalized polar varieties: geometry and algorithms
- Polar varieties and efficient real elimination
- Generalized polar varieties and an efficient real elimination.
- On the geometry and topology of the solution variety for polynomial system solving
- scientific article; zbMATH DE number 2151204
- On the polar varieties of ruled hypersurfaces
- Polyhedral methods in numerical algebraic geometry
Cites Work
- Title not available (Why is that?)
- Factoring polynomials with rational coefficients
- The complexity of partial derivatives
- On the Betti Numbers of Real Varieties
- Straight-line programs in geometric elimination theory
- Boolean circuits versus arithmetic circuits
- Title not available (Why is that?)
- The membership problem for unmixed polynomial ideals is solvable in single exponential time
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Title not available (Why is that?)
- Variétés polaires locales et classes de Chern des variétés singulieres
- Sur la complexité du principe de Tarski-Seidenberg
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's Theorem I: Geometric Aspects
- Solving systems of polynomial inequalities in subexponential time
- On the combinatorial and algebraic complexity of quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Constructions in Algebra
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Efficient incremental algorithms for the sparse resultant and the mixed volume
- Résolution des systèmes d'équations algébriques
- Complexity of deciding Tarski algebra
- Title not available (Why is that?)
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of elementary algebra and geometry
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of computation on real algebraic numbers
- Algèbre linéaire sur $K[X_1,\dots,X_n]$ et élimination
- Title not available (Why is that?)
- Algorithms in algebraic geometry and applications. Proceedings of the MEGA-94 conference, Santander, Spain, April 5-9, 1994
- Title not available (Why is that?)
Cited In (31)
- A concise proof of the Kronecker polynomial system solver from scratch
- Title not available (Why is that?)
- Estimates on the number of \(\mathbb{F}_q\)-rational solutions of variants of diagonal equations over finite fields
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- Refined bounds on the number of connected components of sign conditions on a variety
- Title not available (Why is that?)
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- On types of isolated KKT points in polynomial optimization
- On the intrinsic complexity of point finding in real singular hypersurfaces
- Polar Varieties Revisited
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- On the geometry of polar varieties
- Fast computation of a rational point of a variety over a finite field
- Deformation techniques for efficient polynomial equation solving.
- Polar varieties, Bertini's theorems and number of points of singular complete intersections over a finite field
- Generalized polar varieties: geometry and algorithms
- Real root finding for determinants of linear matrices
- Faster real root decision algorithm for symmetric polynomials
- On sign conditions over real multivariate polynomials
- Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
- On types of degenerate critical points of real polynomial functions
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Local polar varieties in the geometric study of singularities
- Computing real witness points of positive dimensional polynomial systems
- In memoriam. Succinct obituary in memoriam of Joos Heintz
- Computing the dimension of real algebraic sets
- Title not available (Why is that?)
- Global optimization of polynomials restricted to a smooth variety using sums of squares
Uses Software
This page was built for publication: Polar varieties, real equation solving, and data structures: the hypersurface case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361872)
