Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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

Registro:

Documento: Artículo
Título:Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
Autor:Bank, B.; Giusti, M.; Heintz, J.; Lehmann, L.; Pardo, L.M.
Filiación:Institut für Mathematik, Humboldt-Universität zu Berlin, 10099 Berlin, Germany
CNRS, Lab. LIX, École Polytechnique, 91228 Palaiseau CEDEX, France
Departamento de Computación, Universidad de Buenos Aires and CONICET, Ciudad Univ., Pab. I, 1428 Buenos Aires, Argentina
Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, 39071 Santander, Spain
Palabras clave:Degree of varieties; Intrinsic complexity; Polar and bipolar varieties; Real polynomial equation solving; Singularities
Año:2012
Volumen:12
Número:1
Página de inicio:75
Página de fin:122
DOI: http://dx.doi.org/10.1007/s10208-011-9112-6
Título revista:Foundations of Computational Mathematics
Título revista abreviado:Found. Comput. Math.
ISSN:16153375
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v12_n1_p75_Bank

Referencias:

  • Aubry, P., Rouillier, F., Safey El Din, M., Real solving for positive dimensional systems (2002) J. Symb. Comput., 34, pp. 543-560
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties, real equation solving, and data structures: the hypersurface case (1997) J. Complex., 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, 40, pp. 519-550
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties: geometry and algorithms (2005) J. Complex., 21, pp. 377-412
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., On the intrinsic complexity of point finding in real singular hypersurfaces (2009) Inf. Process. Lett., 109, pp. 1141-1144
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Bipolar varieties and real solving of a singular polynomial equation (2010) Jaen J. Approx., 2 (1), pp. 65-77
  • Bank, B., Giusti, M., Heintz, J., Safey El Din, M., Schost, E., On the geometry of polar varieties (2010) Appl. Algebra Eng. Commun. 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
  • Basu, S., Pollack, R., Roy, M.-F., (2006) Algorithms in Real Algebraic Geometry, , 2nd edn., Berlin: Springer
  • Bochnak, J., Coste, M., Roy, M.-F., (1987) Géométrie Algébrique Réelle, , Berlin: Springer
  • Brasselet, J.P., Milnor classes via polar varieties (2000) Singularities in Algebraic and Analytic Geometry, 266, pp. 181-187. , Contemp. Math, C. G. Melles (Ed.), Providence: AMS
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory, 315. , Grundlehren der Mathematischen Wissenschaftenwith the collaboration of Thomas Lickteig, Berlin: Springer
  • Canny, J.F., Some algebraic and geometric computations in PSPACE (1988) ACM Symposium on Theory of Computing (STOC), 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
  • Coste, M., Roy, M.-F., Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets (1988) J. Symb. Comput., 5, pp. 121-129
  • Demazure, M., (1989) Catastrophes Et Bifurcations, , Paris: Ellipses
  • Dubson, A., (1982) Courants sous-analytiques, théorie d'intersection des ensembles analytiques, invariants numériques des singularités et applications, , Thèse d'État, Université Paris VII
  • Durvye, C., Evaluation techniques for zero-dimensional primary decomposition (2009) J. Symb. Comput., 44, pp. 1089-1113
  • Durvye, C., Lecerf, G., A concise proof of the Kronecker polynomial system solver from scratch (2008) Expo. Math., 26, pp. 101-139
  • Fitchas, N., Galligo, A., Morgenstern, J., Algorithmes rapides en séquentiel et en parallèle pour l'élimination des quantificateurs en géométrie élémentaire (1990) Publ. Math. Univ. Paris VII, 32, pp. 103-145. , Structures algébriques ordonnées, Volume I, Sélect. Expos. Sémin., Paris, 1984-1987
  • Fulton, W., (1998) Intersection Theory, 3. , 2nd edn., Ergebnisse der Mathematik und ihrer GrenzgebieteFolge 2, Berlin: Springer
  • Giusti, M., Heintz, J., Kronecker's smart, little black boxes (2001) Foundations of Computational Mathematics, 284, pp. 69-104. , ConferenceOxford, GBJuly 18-28, 1999Lond. Math. Soc. Lect. Note Ser, R. A. DeVore (Ed.), Cambridge: Cambridge University Press
  • Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be "solved" fast? (1995) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 948, pp. 205-231. , LNCS, G. Cohen, M. Giusti, and T. Mora (Eds.), Berlin: Springer
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for Diophantine approximations (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., Le rôle des structures de données dans les problèmes d'élimination (1997) C.R. Acad. Sci. Paris Sér. I Math., 325, pp. 1223-1228
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124, pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complex., 17, pp. 154-211
  • Grigor'ev, D., Vorobjov, N., Solving systems of polynomial inequalities in subexponential time (1988) J. Symb. Comput., 5, pp. 37-64
  • Hägele, K., Montaña, J.L., (1997) Polynomial random test for the equivalence of integers given by arithmetic circuits, p. 4. , Depto. de Matematicas, Estadistica y Computacion, Universidad de Cantabria
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theor. Comput. Sci., 24, pp. 239-277
  • 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: Amsterdam
  • Heintz, J., Roy, M.-F., Solernó, P., Complexité du principe de Tarski-Seidenberg (1989) C.R. Acad. Sci., Paris, Sér. I Math, 309, pp. 825-830
  • Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. Fr., 18, pp. 101-126
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complex., 16, pp. 70-109
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Eng. Commun. Comput., 11, pp. 239-296
  • Henry, J.P.G., Merle, M., Limites d'espaces tangents et transversalité de variétés polaires (1982) Algebraic Geometry, Proc. Int. Conf., La Rabida/Spain 1981, 961, pp. 189-199. , Lect. Notes Math
  • Krick, T., Straight-line programs in polynomial equation solving (2004) Foundations of Computational Mathematics: Minneapolis 2002 (FoCM 2002), 312, pp. 96-136. , London Mathematical Society Lecture Note Ser, F. Cucker (Ed.), Cambridge: Cambridge University Press
  • Lê, D.T., Teissier, B., Variétés polaires locales et classes de Chern des variétés singulières (1981) Ann. Math. (2), 114, pp. 457-491
  • Lecerf, G., Quadratic Newton iteration for systems with multiplicity (2002) Found. Comput. Math., 2, pp. 247-293
  • Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers (2003) J. Complex., 19, pp. 564-596
  • Lecerf, G., Kronecker software package, , http://www.math.uvsq.fr/~lecerf/software/index.html
  • Lehmann, L., (2007) Wavelet-Konstruktion als Anwendung der algorithmischen reellen algebraischen Geometrie, , http://edoc.hu-berlin.de/docviews/abstract.php?lang=ger&id=27952, Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
  • Lehmann, L., Waissbein, A., Wavelets and semi-algebraic sets (2001) WAIT 2001, Anales JAIIO, 30, pp. 139-155. , M. Frias and J. Heintz (Eds.)
  • Mork, H.C., Piene, R., Polars of real singular plane curves (2008) Algorithms in Algebraic Geometry, 146, pp. 99-115. , Minneapolis, MN, USASeptember 18-22, 2006The IMA Volumes in Mathematics and Its Applicationsbased on the workshop, A. Dickenstein (Ed.), New York: Springer
  • Piene, R., Polar classes of singular varieties (1978) Ann. Sci. Éc. Norm. Supér. (4), 11, pp. 247-276
  • Renegar, J., A faster PSPACE algorithm for the existential theory of the reals (1988) Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science, pp. 291-295
  • Renegar, J., On the computational complexity and geometry of the first order theory of the reals (1992) J. Symb. Comput., 13, pp. 255-352
  • Safey El Din, M., (2005) Finding sampling points on real hypersurfaces is easier in singular situations, , Preprint Université Paris VII
  • Safey El Din, M., Schost, E., Polar varieties and computation of one point in each connected component of a smooth real algebraic set (2003) Proc. ISSAC 2003, pp. 224-231. , J. R. Sendra (Ed.), New York: ACM
  • Safey El Din, M., Schost, E., Properness defects and projections and computation of at least one point in each connected component of a real algebraic set (2004) J. Discrete Comput. Geom., 32, pp. 417-430
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Eng. Commun. Comput., 13, pp. 349-393
  • Severi, F., Sulle intersezioni delle varieta algebriche e sopra i loro caratteri e singolarità proiettive (1903) Torino Mem. (2), 52, pp. 61-118
  • Severi, F., La serie canonica e la teoria delle serie principali di gruppi di punti sopra una superficie algebrica (1932) Comment. Math. Helv., 4, pp. 268-326
  • Shafarevich, I.R., (1994) Basic Algebraic Geometry. 1: Varieties in Projective Space, , Berlin: Springer
  • Solernó, P., Effective Lojasiewicz inequalities in semialgebraic geometry (1991) Appl. Algebra Eng. Commun. Comput., 2, pp. 1-14
  • Spivak, M., (1965) Calculus on Manifolds. A Modern Approach to Classical Theorems of Advanced Calculus, , Amsterdam: Benjamins
  • Teissier, B., Variétés polaires II., Multiplicités polaires, sections planes, et conditions de Whitney (1982) Algebraic Geometry, 961, pp. 314-491. , Proc. Int. Conf.La Rabida/Spain1981Lect. Notes Math
  • Teissier, B., Quelques points de l'histoire des variétés polaires, de Poncelet à nos jours (1988) Sémin. Anal., 4, p. 12. , Univ. Blaise Pascal 1987-1988
  • Todd, J.A., The geometrical invariants of algebraic loci (1937) Proc. Lond. Math. Soc., 43, pp. 127-138
  • Todd, J.A., The arithmetical invariants of algebraic loci (1937) Proc. Lond. Math. Soc., 43, pp. 190-225
  • Vogel, W., (1984) Lectures on Results on Bézout's Theorem, 74. , Lectures on Mathematics and PhysicsNotes by D.P. Patil, published for Tata Institute of Fundamental Research, Berlin: Springer
  • von zur Gathen, J., Parallel arithmetic computations: a survey. Mathematical foundations of computer science (1986) Proc. 12th Symp., 233, pp. 93-112. , Bratislava/Czech1986Lect. Notes Comput. Sci
  • von zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithms, pp. 573-617. , J. H. Reif (Ed.), San Mateo: Morgan Kaufmann

Citas:

---------- APA ----------
Bank, B., Giusti, M., Heintz, J., Lehmann, L. & Pardo, L.M. (2012) . Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces. Foundations of Computational Mathematics, 12(1), 75-122.
http://dx.doi.org/10.1007/s10208-011-9112-6
---------- CHICAGO ----------
Bank, B., Giusti, M., Heintz, J., Lehmann, L., Pardo, L.M. "Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces" . Foundations of Computational Mathematics 12, no. 1 (2012) : 75-122.
http://dx.doi.org/10.1007/s10208-011-9112-6
---------- MLA ----------
Bank, B., Giusti, M., Heintz, J., Lehmann, L., Pardo, L.M. "Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces" . Foundations of Computational Mathematics, vol. 12, no. 1, 2012, pp. 75-122.
http://dx.doi.org/10.1007/s10208-011-9112-6
---------- VANCOUVER ----------
Bank, B., Giusti, M., Heintz, J., Lehmann, L., Pardo, L.M. Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces. Found. Comput. Math. 2012;12(1):75-122.
http://dx.doi.org/10.1007/s10208-011-9112-6