Point searching in real singular complete intersection varieties: algorithms of intrinsic complexity
HTML articles powered by AMS MathViewer
- by Bernd Bank, Marc Giusti and Joos Heintz PDF
- Math. Comp. 83 (2014), 873-897 Request permission
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\;|\;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
- 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, DOI 10.1006/jcom.1997.0432
- 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, DOI 10.1007/PL00004896
- 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
- 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, DOI 10.1016/j.jco.2004.10.001
- 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, DOI 10.1007/s00200-009-0117-1
- 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, DOI 10.1016/j.ipl.2009.07.014
- 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
- 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, DOI 10.1007/s10208-011-9112-6
- 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, DOI 10.1145/235809.235813
- 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
- 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, DOI 10.1007/978-3-662-03338-8
- J.F. Canny, Some algebraic and geometric computations in PSPACE, ACM Symposium on Theory of Computing (STOC) (1988), 460-467.
- 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, DOI 10.1007/s10208-002-0065-7
- 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, DOI 10.1016/S0747-7171(88)80008-7
- 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)
- M. Demazure, Catastrophes et bifurcations, Ellipses, Paris 1989.
- 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, DOI 10.1016/j.exmath.2007.07.001
- 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, DOI 10.1007/978-1-4612-1700-8
- M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo, When polynomial equation systems can be “solved” fast?, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995) Lecture Notes in Comput. Sci., vol. 948, Springer, Berlin, 1995, pp. 205–231. MR 1448166, DOI 10.1007/3-540-60114-7_{1}6
- 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, DOI 10.1016/S0022-4049(97)00015-7
- 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, DOI 10.1016/S0022-4049(96)00099-0
- 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
- 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, DOI 10.1006/jcom.2000.0571
- D. Yu. Grigor′ev 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, DOI 10.1016/S0747-7171(88)80005-1
- 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)
- Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, DOI 10.1016/0304-3975(83)90002-6
- 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, DOI 10.1016/j.jco.2012.04.005
- J. Heintz, B. Kuijpers, A. Rojas Paredes, On the intrinsic complexity of elimination problems in effective algebraic geometry, arXiv:1201.4344v3.
- 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, DOI 10.1007/s002000000046
- 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.
- 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
- 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
- George Kempf, On the geometry of a theorem of Riemann, Ann. of Math. (2) 98 (1973), 178–185. MR 349687, DOI 10.2307/1970910
- 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, DOI 10.1016/0096-3003(87)90063-4
- 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.
- 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, DOI 10.1016/S0747-7171(10)80003-3
- T. G. Room, The geometry of determinantal loci, Cambridge Univ. Press (1938).
- F. Severi, Sulle intersezioni delle varieta algebriche e sopra i loro caratteri e singolarita proiettive, Torino Mem. (2) 52 (1903), 61-118.
- 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, DOI 10.1007/BF01202721
- Michael Spivak, Calculus on manifolds. A modern approach to classical theorems of advanced calculus, W. A. Benjamin, Inc., New York-Amsterdam, 1965. MR 0209411
- 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, DOI 10.1007/BFb0071291
- 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-Ferrand, 1990, pp. Exp. No. 4, 12 (French). MR 1088966
- J. A. Todd, The Geometrical Invariants of Algebraic Loci, Proc. London Math. Soc. (2) 43 (1937), no. 2, 127–138. MR 1575589, DOI 10.1112/plms/s2-43.2.127
- J. A. Todd, The Arithmetical Invariants of Algebraic Loci, Proc. London Math. Soc. (2) 43 (1937), no. 3, 190–225. MR 1575915, DOI 10.1112/plms/s2-43.3.190
- 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; by Springer-Verlag, Berlin, 1984. Notes by D. P. Patil. MR 743265, DOI 10.1007/978-3-662-00493-7
- 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, DOI 10.1007/BFb0016236
- J. von zur Gathen, Parallel linear algebra, in Synthesis of parallel algorithms (J. H. Reif, ed.), Kaufmann, San Mateo, CA., 1993, pp. 573–617.
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
- 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.
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3143696