Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity


Authors: Bernd Bank, Marc Giusti and Joos Heintz
Journal: Math. Comp. 83 (2014), 873-897
MSC (2010): Primary 68W30, 14B05, 14P05, 14B07, 68W10
DOI: https://doi.org/10.1090/S0025-5718-2013-02766-4
Published electronically: October 31, 2013
MathSciNet review: 3143696
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ X_1,\ldots ,X_n$ be indeterminates over $ \mathbb{Q}$ and let $ X:=(X_1,\ldots ,$
$ X_n)$. Let $ F_1,\ldots ,F_p$ be a regular sequence of polynomials in $ \mathbb{Q}[X]$ of degree at most $ d$ such that for each $ 1\le k \le p$ the ideal $ (F_1,\ldots , F_k)$ is radical. Suppose that the variables $ X_1,\ldots ,X_n$ are in generic position with respect to $ F_1,\ldots ,F_p$. Further, suppose that the polynomials are given by an essentially division-free circuit $ \beta $ in $ \mathbb{Q}[X]$ of size $ L$ and non-scalar depth $ \ell $.

We present a family of algorithms $ \Pi _i$ and invariants $ \delta _i$ of $ F_1,\ldots ,F_p$, $ 1\le i \le n-p$, such that $ \Pi _i$ produces on input $ \beta $ a smooth algebraic sample point for each connected component of $ \{x\in \mathbb{R}^n\;\vert\;F_1(x)=\cdots =F_p(x)=0\}$ where the Jacobian of $ F_1=0,\ldots , F_p=0$ has generically rank $ p$.

The sequential complexity of $ \Pi _i$ is of order $ L(n\,d)^{O(1)}(\min \{(n\,d)^{c\,n},\delta _i\})^2$ and its non-scalar parallel complexity is of order $ O(n(\ell +\log n\,d)\log \delta _i)$. Here $ c>0$ is a suitable universal constant. Thus, the complexity of $ \Pi _i$ meets the already known worst case bounds. The particular feature of $ \Pi _i$ is its pseudo-polynomial and intrinsic complexity character and this entails the best runtime behavior one can hope for. The algorithm $ \Pi _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 $ (n^n\,d)^{O(n)}$ for the invariant $ \delta _i$. The reader may notice that this bound overestimates the extrinsic complexity of $ \Pi _i$, which is bounded by $ (nd)^{O(n)}$.


References [Enhancements On Off] (What's this?)

  • [1] B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar varieties, real equation solving, and data structures: the hypersurface case, J. Complexity 13 (1997), no. 1, 5-27. MR 1449757 (98h:68123), https://doi.org/10.1006/jcom.1997.0432
  • [2] B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar varieties and efficient real elimination, Math. Z. 238 (2001), no. 1, 115-144. MR 1860738 (2002g:14084), https://doi.org/10.1007/PL00004896
  • [3] Bernd Bank, Marc Giusti, Joos Heintz, and Luis M. Pardo, Generalized polar varieties and an efficient real elimination procedure, Kybernetika (Prague) 40 (2004), no. 5, 519-550. MR 2120995 (2006e:14078)
  • [4] B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, Generalized polar varieties: geometry and algorithms, J. Complexity 21 (2005), no. 4, 377-412. MR 2152713 (2006f:14068), https://doi.org/10.1016/j.jco.2004.10.001
  • [5] Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din, and Eric Schost, On the geometry of polar varieties, Appl. Algebra Engrg. Comm. Comput. 21 (2010), no. 1, 33-83. MR 2585564 (2011c:68065), https://doi.org/10.1007/s00200-009-0117-1
  • [6] Bernd Bank, Marc Giusti, Joos Heintz, and Luis Miguel Pardo, On the intrinsic complexity of point finding in real singular hypersurfaces, Inform. Process. Lett. 109 (2009), no. 19, 1141-1144. MR 2552931 (2010j:68036), https://doi.org/10.1016/j.ipl.2009.07.014
  • [7] Bernd Bank, Marc Giusti, Joos Heintz, and Luis Miguel Pardo, Bipolar varieties and real solving of a singular polynomial equation, Jaen J. Approx. 2 (2010), no. 1, 65-77. MR 2789520 (2012e:14111)
  • [8] Bernd Bank, Marc Giusti, Joos Heintz, Lutz Lehmann, and Luis Miguel Pardo, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Found. Comput. Math. 12 (2012), no. 1, 75-122. MR 2886157, https://doi.org/10.1007/s10208-011-9112-6
  • [9] Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43 (1996), no. 6, 1002-1045. MR 1434910 (98c:03077), https://doi.org/10.1145/235809.235813
  • [10] Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869 (2007b:14125)
  • [11] Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179 (99c:68002)
  • [12] J.F. Canny, Some algebraic and geometric computations in PSPACE, ACM Symposium on Theory of Computing (STOC) (1988), 460-467.
  • [13] D. Castro, M. Giusti, J. Heintz, G. Matera, and L. M. Pardo, The hardness of polynomial equation solving, Found. Comput. Math. 3 (2003), no. 4, 347-420. MR 2009683 (2004k:68056), https://doi.org/10.1007/s10208-002-0065-7
  • [14] M. Coste and M.-F. Roy, Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symbolic Comput. 5 (1988), no. 1-2, 121-129. MR 949115 (89g:12002), https://doi.org/10.1016/S0747-7171(88)80008-7
  • [15] C. D' Andrea, T. Krick, and M. Sombra, Heights of varieties in multi-projective spaces and arithmetic Nullstellensätze, Manuscript, Universidad de Buenos Aires (2011)
  • [16] M. Demazure, Catastrophes et bifurcations, Ellipses, Paris 1989.
  • [17] Clémence Durvye and Grégoire Lecerf, A concise proof of the Kronecker polynomial system solver from scratch, Expo. Math. 26 (2008), no. 2, 101-139. MR 2413831 (2009c:14119), https://doi.org/10.1016/j.exmath.2007.07.001
  • [18] William Fulton, Intersection theory, 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 2, Springer-Verlag, Berlin, 1998. MR 1644323 (99d:14003)
  • [19] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo, When polynomial equation systems can be ``solved'' fast?, (Paris, 1995) Lecture Notes in Comput. Sci., vol. 948, Springer, Berlin, 1995, pp. 205-231. MR 1448166 (98a:68106), https://doi.org/10.1007/3-540-60114-7_16
  • [20] M. Giusti, J. Heintz, K. Hägele, J. E. Morais, L. M. Pardo, and J. L. Montaña, Lower bounds for Diophantine approximations, J. Pure Appl. Algebra 117/118 (1997), 277-317. Algorithms for algebra (Eindhoven, 1996). MR 1457843 (99d:68106), https://doi.org/10.1016/S0022-4049(97)00015-7
  • [21] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo, Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124 (1998), no. 1-3, 101-146. MR 1600277 (99d:68128), https://doi.org/10.1016/S0022-4049(96)00099-0
  • [22] Marc Giusti and Joos Heintz, Kronecker's smart, little black boxes, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 69-104. MR 1836615 (2002e:65075)
  • [23] Marc Giusti, Grégoire Lecerf, and Bruno Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154-211. MR 1817612 (2002b:68123), https://doi.org/10.1006/jcom.2000.0571
  • [24] D. Yu. Grigorev and N. N. Vorobjov Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), no. 1-2, 37-64. MR 949112 (89h:13001), https://doi.org/10.1016/S0747-7171(88)80005-1
  • [25] K. Hägele and J. L. Montaña, Polynomial random test for the equivalence of integers given by arithmetic circuits, Depto. de Matematicas, Estadistica y Computacion, Universidad de Cantabria, 4 (1997)
  • [26] Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239-277. MR 716823 (85a:68062), https://doi.org/10.1016/0304-3975(83)90002-6
  • [27] Joos Heintz, Bart Kuijpers, and Andrés Rojas Paredes, Software Engineering and complexity in effective algebraic geometry, J. Complexity 29 (2013), no. 1, 92-138. MR 2997853, https://doi.org/10.1016/j.jco.2012.04.005
  • [28] J. Heintz, B. Kuijpers, A. Rojas Paredes, On the intrinsic complexity of elimination problems in effective algebraic geometry, arXiv:1201.4344v3.
  • [29] Joos Heintz, Guillermo Matera, and Ariel Waissbein, On the time-space complexity of geometric elimination procedures, Appl. Algebra Engrg. Comm. Comput. 11 (2001), no. 4, 239-296. MR 1818975 (2002c:68108), https://doi.org/10.1007/s002000000046
  • [30] J. Heintz, M.-F. Roy, and P. Solernó, On the complexity of semialgebraic sets, in IFIP Information Processing 89 (G. X. Ritter , ed.), Elsevier, 1989, pp. 293-298.
  • [31] Joos Heintz, Marie-Françoise Roy, and Pablo Solernó, Complexité du principe de Tarski-Seidenberg, C. R. Acad. Sci. Paris Sér. I Math. 309 (1989), no. 13, 825-830 (French, with English summary). MR 1055203 (92c:12012)
  • [32] Joos Heintz, Marie-Françoise Roy, and Pablo Solernó, Sur la complexité du principe de Tarski-Seidenberg, Bull. Soc. Math. France 118 (1990), no. 1, 101-126 (French, with English summary). MR 1077090 (92g:03047)
  • [33] George Kempf, On the geometry of a theorem of Riemann, Ann. of Math. (2) 98 (1973), 178-185. MR 0349687 (50 #2180)
  • [34] Alexander Morgan and Andrew Sommese, A homotopy for solving general polynomial systems that respects $ m$-homogeneous structures, Appl. Math. Comput. 24 (1987), no. 2, 101-113. MR 914806 (88j:65110), https://doi.org/10.1016/0096-3003(87)90063-4
  • [35] J. Renegar, A faster PSPACE algorithm for the existential theory of the reals, in Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science, 1988, pp. 291-295.
  • [36] James Renegar, 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, J. Symbolic Comput. 13 (1992), no. 3, 255-299. MR 1156882 (93h:03011a), https://doi.org/10.1016/S0747-7171(10)80003-3
  • [37] T. G. Room, The geometry of determinantal loci, Cambridge Univ. Press (1938).
  • [38] F. Severi, Sulle intersezioni delle varieta algebriche e sopra i loro caratteri e singolarita proiettive, Torino Mem. (2) 52 (1903), 61-118.
  • [39] Francesco di Severi, La serie canonica e la teoria delle serie principali di gruppi di punti sopra una superficie algebrica, Comment. Math. Helv. 4 (1932), no. 1, 268-326 (Italian). MR 1509461, https://doi.org/10.1007/BF01202721
  • [40] Michael Spivak, Calculus on manifolds. A modern approach to classical theorems of advanced calculus, W. A. Benjamin, Inc., New York-Amsterdam, 1965. MR 0209411 (35 #309)
  • [41] Bernard Teissier, Variétés polaires. II. Multiplicités polaires, sections planes, et conditions de Whitney, Algebraic geometry (La Rábida, 1981) Lecture Notes in Math., vol. 961, Springer, Berlin, 1982, pp. 314-491 (French). MR 708342 (85i:32019), https://doi.org/10.1007/BFb0071291
  • [42] Bernard Teissier, Quelques points de l'histoire des variétés polaires, de Poncelet à nos jours, Séminaire d'Analyse, 1987-1988 (Clermont-Ferrand, 1987-1988) Univ. Clermont-Ferrand II, Clermont, 1990, pp. Exp. No. 4, 12 (French). MR 1088966 (91m:14001)
  • [43] J. A. Todd, The Geometrical Invariants of Algebraic Loci, Proc. London Math. Soc. S2-43, no. 2, 127. MR 1575589, https://doi.org/10.1112/plms/s2-43.2.127
  • [44] J. A. Todd, The Arithmetical Invariants of Algebraic Loci, Proc. London Math. Soc. S2-43, no. 3, 190. MR 1575915, https://doi.org/10.1112/plms/s2-43.3.190
  • [45] W. Vogel, Lectures on results on Bezout's theorem, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 74, Published for the Tata Institute of Fundamental Research, Bombay, 1984. Notes by D. P. Patil. MR 743265 (86f:14003)
  • [46] Joachim von zur Gathen, Parallel arithmetic computations: a survey, Mathematical foundations of computer science, 1986 (Bratislava, 1986), Lecture Notes in Comput. Sci., vol. 233, Springer, Berlin, 1986, pp. 93-112. MR 874591, https://doi.org/10.1007/BFb0016236
  • [47] J. von zur Gathen, Parallel linear algebra, in Synthesis of parallel algorithms (J. H. Reif, ed.), Kaufmann, San Mateo, CA., 1993, pp. 573-617.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 14B05, 14P05, 14B07, 68W10

Retrieve articles in all journals with MSC (2010): 68W30, 14B05, 14P05, 14B07, 68W10


Additional Information

Bernd Bank
Affiliation: Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany
Email: bank@mathematik.hu-berlin.de

Marc Giusti
Affiliation: CNRS, École Polytechnique, Lab. LIX, F-91228 Palaiseau, Cedex, France
Email: marc.giusti@polytechnique.fr

Joos Heintz
Affiliation: 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
Email: joos@dc.uba.ar

DOI: https://doi.org/10.1090/S0025-5718-2013-02766-4
Keywords: Real polynomial equation solving, intrinsic complexity, singularities, polar, copolar and bipolar varieties, degree of variety
Received by editor(s): August 16, 2011
Received by editor(s) in revised form: July 12, 2012
Published electronically: October 31, 2013
Additional Notes: This research was partially supported by the following Argentinian, French and Spanish grants: CONICET PIP 2461/01, UBACYT 20020100100945, PICT–2010–0525, Digiteo DIM 2009–36HD “Magix”, ANR-2010-BLAN-0109-04 “LEDA”, MTM2010-16051.
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society