Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
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.
scientific article; zbMATH DE number 6052410
scientific article