Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces (Q431820): Difference between revisions
From MaRDI portal
Latest revision as of 10:52, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces |
scientific article |
Statements
Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces (English)
0 references
3 July 2012
0 references
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.
0 references
real polynomial solving
0 references
intrinsic complexity
0 references
singularities
0 references
polar and bipolar varieties
0 references
degree of varieties
0 references
0 references
0 references
0 references