Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces |
| |
Authors: | Bernd Bank Marc Giusti Joos Heintz Lutz Lehmann Luis Miguel Pardo |
| |
Institution: | 1. Institut f??r Mathematik, Humboldt-Universit?t zu Berlin, 10099, Berlin, Germany 2. CNRS, Lab. LIX, ??cole Polytechnique, 91228, Palaiseau CEDEX, France 3. Departamento de Computaci??n, Universidad de Buenos Aires and CONICET, Ciudad Univ., Pab. I, 1428, Buenos Aires, Argentina 4. Departamento de Matem??ticas, Estad??stica y Computaci??n, Facultad de Ciencias, Universidad de Cantabria, 39071, Santander, Spain
|
| |
Abstract: | For a real square-free multivariate polynomial F, we treat the general problem of finding real solutions of the equation F=0, provided that the real solution set {F=0}ℝ is compact. We allow that the equation F=0 may have singular real solutions. We are going to decide whether this equation has a non-singular real solution and, if
this is the case, we exhibit one for each generically smooth connected component of {F=0}ℝ. We design a family of elimination algorithms of intrinsic complexity which solves this problem. In the worst case, the complexity of our algorithms does not exceed the already known extrinsic complexity bound of (nd)
O(n) for the elimination problem under consideration, where n is the number of indeterminates of F and d its (positive) degree. In the case that the real variety defined by F is smooth, there already exist algorithms of intrinsic complexity that solve our problem. However, these algorithms cannot
be used in case when F=0 admits F-singular real solutions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|