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:

Let X1, . . .,Xn be indeterminates over Q and let X := (X1, . . . , Xn). Let F1, . . . ,Fp be a regular sequence of polynomials in Q[X] of degree at most d such that for each 1 ≤ k ≤ p the ideal (F1, . . . , Fk) is radical. Suppose that the variables X1, . . .,Xn are in generic position with respect to F1, . . . ,Fp. Further, suppose that the polynomials are given by an essentially division-free circuit β in Q[X] of size L and non-scalar depth l. We present a family of algorithms φi and invariants di of F1, . . . ,Fp, 1 = i = n - p, such that δi produces on input β a smooth algebraic sample point for each connected component of {x ε Rn F1(x) = . . . = Fp(x) = 0} where the Jacobian of F1 = 0, . . . , Fp = 0 has generically rank p. The sequential complexity of πi is of order L(nd)O(1)(min{(nd)cn, δi})2 and its non-scalar parallel complexity is of order O(n(l + lognd) log δi). Here c > 0 is a suitable universal constant. Thus, the complexity of πi meets the already known worst case bounds. The particular feature of πi is its pseudo-polynomial and intrinsic complexity character and this entails the best runtime behavior one can hope for. The algorithm φi works in the non-uniform deterministic as well as in the uniform probabilistic complexity model. We also exhibit a worst case estimate of order (nn d)O(n) for the invariant δi. The reader may notice that this bound overestimates the extrinsic complexity of πi, which is bounded by (nd)O(n). © 2013 American Mathematical Society.

Registro:

Documento: Artículo
Título:Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity
Autor:Bank, B.; Giusti, M.; Heintz, J.
Filiación:Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany
CNRS, École Polytechnique, Lab. LIX, F-91228 Palaiseau, Cedex, France
Departamento de Computación, Universidad de Buenos Aires, CONICET, Ciudad Universitaria, Pabellon I, 1428 Buenos Aires, Argentina
Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, Avda. de los Castros, E-39005 Santander, Spain
Palabras clave:Copolar and bipolar varieties; Degree of variety; Intrinsic complexity; Polar; Real polynomial equation solving; Singularities
Año:2014
Volumen:83
Número:286
Página de inicio:873
Página de fin:897
DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02766-4
Título revista:Mathematics of Computation
Título revista abreviado:Math. Comput.
ISSN:00255718
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v83_n286_p873_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 (1), pp. 5-27. , DOI 10.1006/jcom.1997.0432. MR1449757 (98h:68123)
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z., 238 (1), pp. 115-144. , DOI 10.1007/PL00004896. MR1860738 (2002g:14084)
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties and an efficient real elimination procedure (2004) Kybernetika, 40 (5), pp. 519-550. , (Prague) MR2120995 (2006e:14078)
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties: geometry and algorithms (2005) J. Complexity, 21 (4), pp. 377-412. , DOI 10.1016/j.jco.2004.10.001. MR2152713 (2006f:14068)
  • Bank, B., Giusti, M., Heintz, J., El Din, M.S., Schost, E., On the geometry of polar varieties (2010) Appl. Algebra Engrg. Comm. Comput., 21 (1), pp. 33-83. , DOI 10.1007/s00200-009-0117-1. MR2585564 (2011c:68065)
  • Bank, B., Giusti, M., Heintz, J., Pardo, M.L., On the intrinsic complexity of point finding in real singular hypersurfaces (2009) Inform. Process. Lett., 109 (19), pp. 1141-1144. , DOI 10.1016/j.ipl.2009.07.014. MR2552931 (2010j:68036)
  • Bank, B., Giusti, M., Heintz, J., Miguel Pardo, L., Bipolar varieties and real solving of a singular polynomial equation (2010) Jaen J. Approx., 2 (1), pp. 65-77. , MR2789520 (2012e:14111)
  • Bank, B., Giusti, M., Heintz, J., Lehmann, L., Miguel Pardo, L., Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces (2012) Found. Comput. Math., 12 (1), pp. 75-122. , DOI 10.1007/s10208-011-9112-6. MR2886157
  • Basu, S., Pollack, B., Marie-Françoise, R., On the combinatorial and algebraic complexity of quantifier elimination (1996) J. ACM, 43 (6), pp. 1002-1045. , DOI 10.1145/235809.235813. MR1434910 (98c:03077)
  • Basu, S., Pollack, R., Marie-Françoise, R., Algorithms in real algebraic geometry (2006), 10. , 2nd ed., Algorithms and Computation in Mathematics, Springer-Verlag, Berlin, MR2248869 (2007b:14125); Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] (1997), 315. , Springer-Verlag, Berlin, With the collaboration of Thomas Lickteig. MR1440179 (99c:68002); Canny, J.F., Some algebraic and geometric computations in PSPACE (1988), pp. 460-467. , ACM Symposium on Theory of Computing (STOC); Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3 (4), pp. 347-420. , DOI 10.1007/s10208-002- 0065-7. MR2009683 (2004k:68056)
  • Coste, M., Roy, M.-F., Lemma, T., the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets (1988) J. Symbolic Comput., 5 (1-2), pp. 121-129. , DOI 10.1016/S0747-7171(88)80008-7. MR949115 (89g:12002)
  • D' Andrea, C., Krick, T., Sombra, M., Heights of varieties in multi-projective spaces and arithmetic Nullstellensätze, Manuscript (2011), Universidad de Buenos Aires; Demazure, M., Catastrophes et bifurcations (1989), Ellipses, Paris; Durvye, C., Lecerf, G., A concise proof of the Kronecker polynomial system solver from scratch (2008) Expo. Math., 26 (2), pp. 101-139. , DOI 10.1016/j.exmath.2007.07.001. MR2413831 (2009c:14119)
  • Fulton, W., Intersection theory, 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete (1998), 2. , 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], Springer- Verlag, Berlin, MR1644323 (99d:14003); Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be "solved" fast? (1995) Lecture Notes in Comput. Sci., 948, pp. 205-231. , (Paris, 1995)Springer, Berlin, DOI 10.1007/3-540-60114-7 16. MR1448166 (98a:68106)
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Pardo, L.M., Montana, J.L., Lower bounds for Diophantine approximations (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317. , DOI 10.1016/S0022-4049(97)00015-7. Algorithms for algebra (Eindhoven, 1996). MR1457843 (99d:68106)
  • 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 (1-3), pp. 101-146. , DOI 10.1016/S0022-4049(96)00099-0. MR1600277 (99d:68128)
  • Giusti, M., Heintz, J., Kronecker's smart, little black boxes, Foundations of computational mathematics (Oxford, 1999) (2001) LondonMath. Soc. Lecture Note Ser., 284, pp. 69-104. , Cambridge Univ. Press, Cambridge, MR1836615 (2002e:65075)
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211. , DOI 10.1006/jcom.2000.0571. MR1817612 (2002b:68123)
  • Grigor'ev, Y.D., Vorobjov, N.N., Solving systems of polynomial inequalities in subexponential time (1988) J. Symbolic Comput., 5 (1-2), pp. 37-64. , DOI 10.1016/S0747- 7171(88)80005-1. MR949112 (89h:13001)
  • Hägele, K., Montana, J.L., Polynomial random test for the equivalence of integers given by arithmetic circuits (1997), 4. , Depto. de Matematicas, Estadistica y Computacion, Universidad de Cantabria; Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277. , DOI 10.1016/0304-3975(83)90002-6. MR716823 (85a:68062)
  • Heintz, J., Kuijpers, B., Rojas Paredes, A., Software Engineering and complexity in effective algebraic geometry (2013) J. Complexity, 29 (1), pp. 92-138. , DOI 10.1016/j.jco.2012.04.005. MR2997853
  • Heintz, J., Kuijpers, B., Rojas Paredes, A., Rojas Paredes, On the intrinsic complexity of elimination problems in effective algebraic geometry arXiv:1201.4344v3; Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Engrg. Comm. Comput., 11 (4), pp. 239-296. , DOI 10.1007/s002000000046. MR1818975 (2002c:68108)
  • Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989), pp. 293-298. , in IFIP Information Processing 89 (G. X. Ritter , ed.), Elsevier; Heintz, J., Marie-Françoise, R., Solernó, P., ComplexitÉ du principe de Tarski- Seidenberg, C. R. Acad. Sci. Paris SÉr. I Math. (French, with English summary). MR1055203 (92c:12012) (1989), 309 (13), pp. 825-830; Heintz, J., Marie-Françoise, R., Solernó, P., Sur la complexitÉ du principe de Tarski- Seidenberg (1990) Bull. Soc. Math. France, 118 (1), pp. 101-126. , (French, with English summary). MR1077090 (92g:03047)
  • Kempf, G., On the geometry of a theorem of Riemann (1973) Ann. of Math., 98 (2), pp. 178-185. , MR0349687 (50 #2180)
  • Morgan, A., Sommese, A., A homotopy for solving general polynomial systems that respects m-homogeneous structures (1987) Appl. Math. Comput., 24 (2), pp. 101-113. , DOI 10.1016/0096-3003(87)90063-4. MR914806 (88j:65110)
  • Renegar, J., A faster PSPACE algorithm for the existential theory of the reals (1988), pp. 291-295. , in Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science; 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. , DOI 10.1016/S0747-7171(10)80003-3. MR1156882 (93h:03011a)
  • Room, T.G., The geometry of determinantal loci (1938), Cambridge Univ. Press; Severi, F., Sulle intersezioni delle varieta algebriche e sopra i loro caratteri e singolarita proiettive (1903) Torino Mem., 52 (2), pp. 61-118
  • di Severi, F., La serie canonica e la teoria delle serie principali di gruppi di punti sopra una superficie algebrica (1932) Comment. Math. Helv., 4 (1), pp. 268-326. , DOI 10.1007/BF01202721 (Italian). MR1509461
  • Spivak, M., Calculus on manifolds. A modern approach to classical theorems of advanced calculus (1965), W. A. Benjamin, Inc., New York-Amsterdam, MR0209411 (35 #309); Teissier, B., Polaires, V., II. MultiplicitÉs polaires, sections planes, et conditions de Whitney, Algebraic geometry (La Rábida, 1981) (1982), 961, pp. 314-491. , Lecture Notes in Math.Springer, Berlin, DOI 10.1007/BFb0071291 (French). MR708342 (85i:32019); Teissier, B., Quelques points de l'histoire des variÉtÉs polaires, de Poncelet a nos jours, SÉminaire d'Analyse, 1987-1988 (Clermont-Ferrand, 1987) (1990), Univ. Clermont-Ferrand II, Clermont, pp. Exp. No. 4, 12 (French). MR1088966 (91m:14001); Todd, J.A., The Geometrical Invariants of Algebraic Loci Proc. London Math. Soc., 127 (2), pp. S2-43. , DOI 10.1112/plms/s2-43.2.127. MR1575589
  • Todd, J.A., The Arithmetical Invariants of Algebraic Loci Proc. London Math. Soc., 190 (3), pp. S2-43. , DOI 10.1112/plms/s2-43.3.190. MR1575915
  • Vogel, W., Lectures on results on Bezout's theorem, Tata Institute of Fundamental Research Lectures on Mathematics and Physics (1984), 74. , Published for the Tata Institute of Fundamental Research, Bombay, Notes by D. P. Patil. MR743265 (86f:14003); von zur Gathen, J., Parallel arithmetic computations: a survey, Mathematical foundations of computer science (1986) Lecture Notes in Comput. Sci.,, 233, pp. 93-112. , 1986 (Bratislava, 1986), Springer, Berlin, DOI 10.1007/BFb0016236. MR874591
  • von zur Gathen, J., Parallel linear algebra (1993), pp. 573-617. , Synthesis of parallel algorithms (J. H. Reif, ed.), Kaufmann, San Mateo, CA

Citas:

---------- APA ----------
Bank, B., Giusti, M. & Heintz, J. (2014) . Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity. Mathematics of Computation, 83(286), 873-897.
http://dx.doi.org/10.1090/S0025-5718-2013-02766-4
---------- CHICAGO ----------
Bank, B., Giusti, M., Heintz, J. "Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity" . Mathematics of Computation 83, no. 286 (2014) : 873-897.
http://dx.doi.org/10.1090/S0025-5718-2013-02766-4
---------- MLA ----------
Bank, B., Giusti, M., Heintz, J. "Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity" . Mathematics of Computation, vol. 83, no. 286, 2014, pp. 873-897.
http://dx.doi.org/10.1090/S0025-5718-2013-02766-4
---------- VANCOUVER ----------
Bank, B., Giusti, M., Heintz, J. Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity. Math. Comput. 2014;83(286):873-897.
http://dx.doi.org/10.1090/S0025-5718-2013-02766-4