Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2012
Materias:
Degree of varieties
Intrinsic complexity
Polar and bipolar varieties
Real polynomial equation solving
Singularities
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v12_n1_p75_Bank
http://hdl.handle.net/20.500.12110/paper_16153375_v12_n1_p75_Bank
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_16153375_v12_n1_p75_Bank
record_format dspace
spelling paper:paper_16153375_v12_n1_p75_Bank2023-06-08T16:25:20Z Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces Degree of varieties Intrinsic complexity Polar and bipolar varieties Real polynomial equation solving Singularities 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. An elimination algorithm of intrinsic complexity presupposes that the polynomial F is encoded by an essentially division-free arithmetic circuit of size L (i. e., F can be evaluated by means of L additions, subtractions and multiplications, using scalars from a previously fixed real ground field, say ℚ) and that there is given an invariant δ(F) which (roughly speaking) depends only on the geometry of the complex hypersurface defined by F. The complexity of the algorithm (measured in terms of the number of arithmetic operations in ℚ) is then linear in L and polynomial in n,d and δ(F). In order to find such a geometric invariant δ(F), we consider suitable incidence varieties which in fact are algebraic families of dual polar varieties of the complex hypersurface defined by F. The generic dual polar varieties of these incidence varieties are called bipolar varieties of the equation F=0. The maximal degree of these bipolar varieties then becomes the essential ingredient of our invariant δ(F). © 2011 SFoCM. 2012 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v12_n1_p75_Bank http://hdl.handle.net/20.500.12110/paper_16153375_v12_n1_p75_Bank
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Degree of varieties
Intrinsic complexity
Polar and bipolar varieties
Real polynomial equation solving
Singularities
spellingShingle Degree of varieties
Intrinsic complexity
Polar and bipolar varieties
Real polynomial equation solving
Singularities
Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
topic_facet Degree of varieties
Intrinsic complexity
Polar and bipolar varieties
Real polynomial equation solving
Singularities
description 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. An elimination algorithm of intrinsic complexity presupposes that the polynomial F is encoded by an essentially division-free arithmetic circuit of size L (i. e., F can be evaluated by means of L additions, subtractions and multiplications, using scalars from a previously fixed real ground field, say ℚ) and that there is given an invariant δ(F) which (roughly speaking) depends only on the geometry of the complex hypersurface defined by F. The complexity of the algorithm (measured in terms of the number of arithmetic operations in ℚ) is then linear in L and polynomial in n,d and δ(F). In order to find such a geometric invariant δ(F), we consider suitable incidence varieties which in fact are algebraic families of dual polar varieties of the complex hypersurface defined by F. The generic dual polar varieties of these incidence varieties are called bipolar varieties of the equation F=0. The maximal degree of these bipolar varieties then becomes the essential ingredient of our invariant δ(F). © 2011 SFoCM.
title Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
title_short Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
title_full Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
title_fullStr Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
title_full_unstemmed Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
title_sort algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
publishDate 2012
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v12_n1_p75_Bank
http://hdl.handle.net/20.500.12110/paper_16153375_v12_n1_p75_Bank
_version_ 1768542663574814720

Ejemplares similares