Polar varieties, real equation solving, and data structures: the hypersurface case
From MaRDI portal
(Redirected from Publication:1361872)
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.
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
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 3890725 (Why is no real title available?)
- scientific article; zbMATH DE number 4154415 (Why is no real title available?)
- scientific article; zbMATH DE number 3759547 (Why is no real title available?)
- scientific article; zbMATH DE number 193784 (Why is no real title available?)
- scientific article; zbMATH DE number 3461174 (Why is no real title available?)
- scientific article; zbMATH DE number 4123298 (Why is no real title available?)
- scientific article; zbMATH DE number 599115 (Why is no real title available?)
- scientific article; zbMATH DE number 1057737 (Why is no real title available?)
- scientific article; zbMATH DE number 1057749 (Why is no real title available?)
- scientific article; zbMATH DE number 3188124 (Why is no real title available?)
- Algorithms in algebraic geometry and applications. Proceedings of the MEGA-94 conference, Santander, Spain, April 5-9, 1994
- Algèbre linéaire sur $K[X_1,\dots,X_n]$ et élimination
- Boolean circuits versus arithmetic circuits
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity of computation on real algebraic numbers
- Complexity of deciding Tarski algebra
- Constructions in Algebra
- Efficient incremental algorithms for the sparse resultant and the mixed volume
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Factoring polynomials with rational coefficients
- On the Betti Numbers of Real Varieties
- 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
- Résolution des systèmes d'équations algébriques
- Solving systems of polynomial inequalities in subexponential time
- Straight-line programs in geometric elimination theory
- Sur la complexité du principe de Tarski-Seidenberg
- The complexity of elementary algebra and geometry
- The complexity of partial derivatives
- The membership problem for unmixed polynomial ideals is solvable in single exponential time
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- Variétés polaires locales et classes de Chern des variétés singulieres
Cited in
(32)- Polar varieties, Bertini's theorems and number of points of singular complete intersections over a finite field
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case
- On the intrinsic complexity of point finding in real singular hypersurfaces
- Local polar varieties in the geometric study of singularities
- Estimates on the number of \(\mathbb{F}_q\)-rational solutions of variants of diagonal equations over finite fields
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- Generalized polar varieties: geometry and algorithms
- Refined bounds on the number of connected components of sign conditions on a variety
- scientific article; zbMATH DE number 2151204 (Why is no real title available?)
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Generalized polar varieties and an efficient real elimination.
- Real root finding for determinants of linear matrices
- A concise proof of the Kronecker polynomial system solver from scratch
- On sign conditions over real multivariate polynomials
- Polar varieties revisited
- On types of isolated KKT points in polynomial optimization
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- Fast computation of a rational point of a variety over a finite field
- Computing real witness points of positive dimensional polynomial systems
- A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
- Deformation techniques for efficient polynomial equation solving.
- Faster real root decision algorithm for symmetric polynomials
- scientific article; zbMATH DE number 1552220 (Why is no real title available?)
- Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- In memoriam. Succinct obituary in memoriam of Joos Heintz
- Computing the dimension of real algebraic sets
- On types of degenerate critical points of real polynomial functions
- On the geometry of polar varieties
- Global optimization of polynomials restricted to a smooth variety using sums of squares
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)
