Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte la política de Acceso Abierto del editor

Abstract:

We introduce the concept of a bipolar variety of a real algebraic hypersurface. This notion is then used for the design and complexity estimations of a novel type of algorithms that finds algebraic sample points for the connected components of a singular real hypersurface. The complexity of these algorithms is polynomial in the maximal geometric degree of the bipolar varieties of the given hypersurface and in this sense intrinsic. © 2010 Universidad de Jaén.

Registro:

Documento: Artículo
Título:Bipolar varieties and real solving of a singular polynomial equation
Autor:Bank, B.; Giusti, M.; Heint, J.; Pardo, L.M.
Filiación:Humboldt-Universität zu Berlin, Institut für Mathematik, 10099 Berlin, Germany
CNRS, Lab. LIX, École Polytechnique, 91228 Palaiseau Cedex, France
Departamento de Computación, Universidad de Buenos Aires and CONICET, Ciudad University, Pab.I, 1428 Buenos Aires, Argentina
Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, 39071 Santander, Spain
Palabras clave:Polar varieties; Real polynomial equation solving; Singular hypersurface
Año:2010
Volumen:2
Número:1
Página de inicio:65
Página de fin:77
Título revista:Jaen Journal on Approximation
Título revista abreviado:Jaen J. Approx.
ISSN:18893066
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18893066_v2_n1_p65_Bank

Referencias:

  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties, real equation solving and data structures: The hypersurface case (1997) J. Complexity, 13, pp. 5-27
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z., 238, pp. 115-144
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties and an efficient real elimination procedure (2004) Kybernetika (Prague), 40, pp. 519-550
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties: Geometry and algorithms (2005) J. Complexity, 21, pp. 377-412
  • Bank, B., Giusti, M., Heintz, J., Safey El Din, M., Schost, E., On the geometry of polar varieties (2010) Appl. Algebra Engrg. Comm. Comput., 21, pp. 33-83
  • Basu, S., Pollack, R., Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination (1996) J. ACM, 43, pp. 1002-1045
  • Brasselet, J.P., Milnor classes via polar varieties, AMS (2000) Contemp. Math., 266, pp. 181-187
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic complexity theory. With the collaboration of Thomas Lickteig, , [B] Grundlehren der Mathematischen Wissenschaften 315, Springer-Verlag, Berlin
  • Canny, J.F., Some Algebraic and Geometric Computations in PSPACE (1988) Proc. 20th ACM Symp. on Theory of Computing, pp. 460-467
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3, pp. 347-420
  • Giusti, M., Heintz, J., Kronecker's smart, little black boxes (2001) Foundations of Computational Mathematics, Conf, 284, pp. 69-104. , R.A. DeVore, A. Iserles, E. Süli (eds.), Oxford 1999, Cambridge University Press, Lond. Math. Soc. Lect. Note Ser
  • Grigor'ev, D., Vorobjov, N., Solving systems of polynomial inequalities in subexponential time (1988) J. Symb. Comput., 5, pp. 37-64
  • Heintz, J., Kuijpers, B., Constraint databases, data structures and efficient query evaluation (2004) Constraint databases, Proceedings of the First international symposium, pp. 1-24. , B. Kuijpers et al. (eds.), CDB 2004, Paris (France), June 12-13 2004, Lecture Notes in Computer Science 3074, Springer-Verlag, Berlin
  • Henry, J.P.G., Merle, M., Limites d'espaces tangents et transversalité de variétés polaires (1982) Algebraic geometry, Proc. int. Conf., 961, pp. 189-199. , La Rabida (Spain) 1981 Lect. Notes Math
  • Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989) IFIP Information Processing 89, pp. 293-298. , G.X. Ritter (ed.), Elsevier
  • Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. Fr., 118, pp. 101-126
  • Lê, D.T., Teissier, B., Variétés polaires locales et classes de Chern des variétés singuli'eres (1981) Ann. Math., 114 (2), pp. 457-491
  • Mumford, D., Fogarty, J., Kirwan, F., (1994) Geometric Invariant Theory, , Springer-Verlag, Berlin
  • Piene, R., Polar classes of singular varieties (1978) Ann. Scient. éc. Norm. Sup. 4. Sér., 11, pp. 247-276
  • Renegar, J., A faster PSPACE algorithm for deciding the existential theory of the reals (1988) Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 291-295
  • Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals (1992) J. Symbolic Comput., 13 (3), pp. 255-299
  • Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination (1992) J. Symbolic Comput., 13 (3), pp. 301-327
  • Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination (1992) J. Symbolic Comput., 13 (3), pp. 329-352
  • Room, T.G., (1938) The Geometry of Determinantal Loci, , Cambridge University Press, London
  • Rouillier, F., Roy, M.-F., Safey El Din, M., Finding at least one point in each connected component of a real algebraic set defined by a single equation (2000) J. Complexity, 16, pp. 716-750
  • Safey El Din, M., Schost, E., Polar varieties and computation of one point in each connected component of a smooth real algebraic set (2003) Proceedings of ISSAC 2003, pp. 224-231. , J. Rafael (ed.), ACM Press
  • Safey El Din, M., Schost, E., Properness defects of projections and computation of at least one point in each connected component of a real algebraic set (2004) J. Discrete and Comput. Geom., 32, pp. 417-430
  • Safey El Din, M., (2005) Finding sampling points on real hypersurfaces is easier in singular situations, , preprint
  • Teissier, B., Variétes polaires. II. Multiplicités polaires, sections planes, et conditions de Whitney (1982) Algebraic geometry, Proc. Int. Conf., 961, pp. 314-491. , La Rabida (Spain) 1981, Lect. Notes Math
  • Teissier, B., (1988) Quelques points de l'histoire des variétés polaires, de Poncelet 'a nos jours, p. 4. , Sémin. Anal., Univ. Blaise Pascal 1987-1988

Citas:

---------- APA ----------
Bank, B., Giusti, M., Heint, J. & Pardo, L.M. (2010) . Bipolar varieties and real solving of a singular polynomial equation. Jaen Journal on Approximation, 2(1), 65-77.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18893066_v2_n1_p65_Bank [ ]
---------- CHICAGO ----------
Bank, B., Giusti, M., Heint, J., Pardo, L.M. "Bipolar varieties and real solving of a singular polynomial equation" . Jaen Journal on Approximation 2, no. 1 (2010) : 65-77.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18893066_v2_n1_p65_Bank [ ]
---------- MLA ----------
Bank, B., Giusti, M., Heint, J., Pardo, L.M. "Bipolar varieties and real solving of a singular polynomial equation" . Jaen Journal on Approximation, vol. 2, no. 1, 2010, pp. 65-77.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18893066_v2_n1_p65_Bank [ ]
---------- VANCOUVER ----------
Bank, B., Giusti, M., Heint, J., Pardo, L.M. Bipolar varieties and real solving of a singular polynomial equation. Jaen J. Approx. 2010;2(1):65-77.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18893066_v2_n1_p65_Bank [ ]