Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
type: Item
instance of: scholarly article
title: Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
zbMATH Open document ID: 1246.14071
author: Bernd Bank
author: Marc Giusti
author: Joos Heintz
author: Lutz Lehmann
author: Luis Miguel Pardo
published in: Foundations of Computational Mathematics
publication date: 2012-07-03T00:00:00Z
review text: Let \(F\in \mathbb{Q}[X]\) be a polynomial of degree \(d\) such that \(S=V (F=0)\) admits one regular real solution (i.e. the gradient of \(F\) does not vanish). The problem is treated of finding real solutions of \(F=0\) in \(\mathbb{R}^n\). In case that \(F\) is squarefree and the real variety defined by \(F\) is smooth there exist already algorithms of intrinsic complexity to find real solutions of \(F=0\) (cf. [\textit{B. Bank, M. Guisti, J. Heintz} and \textit{G. M. Mbakop}, ``Polar varieties, real equation solving and data structures: the hypersurface case'', J. Complexity 13, No. 1, 5--27 (1997; Zbl 0872.68066)]. In this case an intrinsic invariant \(\delta(F)\) is used which essentially determines the complexity of the algorithm and is a combination of the degree \(d\) with the maximal degree of the generic polar varieties of suitable type. The introduction of the dual polar variety was necessary for the case when \(S_{\mathbb{R}}\) is unbounded. In this situation some of the generic polar varieties of \(S\) may have an empty intersection with \(S_{\mathbb{R}}\). The dual polar varieties can be considered as the complex counterpart of Lagrange-multipliers. The aim of the paper is to solve the problem in case of the existence of singular solutions. Two discrete families of algorithms are presented which solve the problem in the particular case of a complex hypersurface containing smooth real points and possibly also real singularities, one in the case that \(S\) is compact and another without this assumption.
reviewed by: Gerhard Pfister
Mathematics Subject Classification ID: 14P05
Mathematics Subject Classification ID: 14B05
Mathematics Subject Classification ID: 14B07
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 6052410
zbMATH Keywords: real polynomial solving
zbMATH Keywords: intrinsic complexity
zbMATH Keywords: singularities
zbMATH Keywords: polar and bipolar varieties
zbMATH Keywords: degree of varieties
describes a project that uses: Kronecker
describes a project that uses: RAGlib
MaRDI profile type: Publication
full work available at URL: s10208-011-9112-6
OpenAlex ID: W2016419624
cites work: Real solving for positive dimensional systems.
cites work: Polar varieties, real equation solving, and data structures: the hypersurface case
cites work: Polar varieties and efficient real elimination
cites work: Q5389777
cites work: Generalized polar varieties: geometry and algorithms
cites work: On the intrinsic complexity of point finding in real singular hypersurfaces
cites work: Bipolar varieties and real solving of a singular polynomial equation
cites work: On the geometry of polar varieties
cites work: On the combinatorial and algebraic complexity of quantifier elimination
cites work: Algorithms in real algebraic geometry
cites work: Q4762414
cites work: Q4331740
cites work: The hardness of polynomial equation solving
cites work: Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
cites work: Q4386742
cites work: Evaluation techniques for zero-dimensional primary decomposition
cites work: A concise proof of the Kronecker polynomial system solver from scratch
cites work: Q4342000
cites work: Kronecker's smart, little black boxes
cites work: Q4352797
cites work: Lower bounds for diophantine approximations
cites work: Le rôle des structures de données dans les problèmes d'élimination
cites work: Straight-line programs in geometric elimination theory
cites work: A Gröbner free alternative for polynomial system solving
cites work: Solving systems of polynomial inequalities in subexponential time
cites work: Definability and fast quantifier elimination in algebraically closed fields
cites work: Q3483265
cites work: Deformation techniques for efficient polynomial equation solving.
cites work: On the time-space complexity of geometric elimination procedures
cites work: Q5482450
cites work: Variétés polaires locales et classes de Chern des variétés singulieres
cites work: Quadratic Newton iteration for systems with multiplicity
cites work: Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
cites work: Q3521226
cites work: Polars of real singular curves
cites work: Polar classes of singular varieties
cites work: Q1185456
cites work: Q4660671
cites work: Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
cites work: Computing parametric geometric resolutions
cites work: La serie canonica e la teoria delle serie principali di gruppi di punti sopra una superficie algebrica
cites work: Q4302493
cites work: Effective Łojasiewicz inequalities in semialgebraic geometry
cites work: Q5515507
cites work: The Geometrical Invariants of Algebraic Loci
cites work: The Arithmetical Invariants of Algebraic Loci
cites work: Lectures on results on Bezout's theorem. Notes by D. P. Patil
cites work: Q4725742
DOI: 10.1007/S10208-011-9112-6
description: scientific article; zbMATH DE number 6052410