Generalized polar varieties: geometry and algorithms

DOI10.1016/j.jco.2004.10.001zbMath1085.14047OpenAlexW2006394656MaRDI QIDQ2387411

Joos Heintz, Bernd Bank, Marc Giusti, Luis Miguel Pardo

Publication date: 2 September 2005

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2004.10.001

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Singularities in algebraic geometry (14B05) Real algebraic sets (14P05) Computational aspects in algebraic geometry (14Q99)

Related Items

Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients, Local polar varieties in the geometric study of singularities, Refined F5 Algorithms for Ideals of Minors of Square Matrices, Faster real root decision algorithm for symmetric polynomials, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, Early Ending in Homotopy Path-Tracking for Real Roots, Global optimization of polynomials restricted to a smooth variety using sums of squares, Real root finding for determinants of linear matrices, Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Polar varieties, Bertini's theorems and number of points of singular complete intersections over a finite field, A hybrid procedure for finding real points on a real algebraic set, Solving determinantal systems using homotopy techniques, A numerical algorithm for zero counting. I: Complexity and accuracy, Intrinsic complexity estimates in polynomial optimization, Certified non-conservative tests for the structural stability of discrete multidimensional systems, On sign conditions over real multivariate polynomials, On the geometry of polar varieties, On the intrinsic complexity of point finding in real singular hypersurfaces, On exact Reznick, Hilbert-Artin and Putinar's representations, Polar Varieties Revisited, Unnamed Item, Fast computation of a rational point of a variety over a finite field, Degeneracy loci and polynomial equation solving, Bit complexity for computing one point in each connected component of a smooth real algebraic set, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity

Uses Software

• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
• Definability and fast quantifier elimination in algebraically closed fields
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• Solving systems of polynomial inequalities in subexponential time
• Variétés polaires locales et classes de Chern des variétés singulieres
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Probabilistic algorithms for geometric elimination
• Lower bounds for diophantine approximations
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Straight-line programs in geometric elimination theory
• The hardness of polynomial equation solving
• Quadratic Newton iteration for systems with multiplicity
• Real solving for positive dimensional systems.
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Complexity estimates depending on condition and round-off error
• Ideals defined by matrices and a certain complex associated with them
• Computing Powers in Parallel
• Polar classes of singular varieties
• On the combinatorial and algebraic complexity of quantifier elimination
• R-SEQUENCES AND INDETERMINATES
• Sur la complexité du principe de Tarski-Seidenberg
• On the time-space complexity of geometric elimination procedures
• A Gröbner free alternative for polynomial system solving
• Kronecker's and Newton's approaches to solving: a first comparison
• Polar varieties and efficient real elimination