[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Deformation Techniques for Sparse Systems

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E.L. Allgower, K. Georg, Numerical Continuation Methods: An Introduction. Springer Ser. Comput. Math., vol. 13 (Springer, New York, 1990).

    MATH  Google Scholar 

  2. M.E. Alonso, E. Becker, M.-F. Roy, T. Wörmann, Zeros, multiplicities and idempotents for zero-dimensional systems, in Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA’94. Prog. Math., vol. 143 (Birkhäuser, Boston, 1996), pp. 1–15.

    Google Scholar 

  3. J.L. Balcázar, J. Díaz, J. Gabarró, Structural Complexity I. Monogr. Theor. Comput. Sci. EATCS Ser., vol. 11 (Springer, Berlin, 1988).

    MATH  Google Scholar 

  4. W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci. 22, 317–330 (1983).

    Article  MATH  MathSciNet  Google Scholar 

  5. D.N. Bernstein, The number of roots of a system of equations, Funct. Anal. Appl. 9, 183–185 (1975).

    Article  MATH  Google Scholar 

  6. D. Bini, V. Pan, Polynomial and Matrix Computations. Progress in Theoretical Computer Science (Birkhäuser, Boston, 1994).

    MATH  Google Scholar 

  7. L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1998).

    Google Scholar 

  8. A. Bompadre, G. Matera, R. Wachenchauzer, A. Waissbein, Polynomial equation solving by lifting procedures for ramified fibers, Theoret. Comput. Sci. 315(2–3), 335–369 (2004).

    Article  MATH  MathSciNet  Google Scholar 

  9. A. Bostan, G. Lecerf, E. Schost, Tellegen’s principle into practice, in Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’03), Philadelphia, PA, 3–6 August 2003, ed. by J.R. Sendra (ACM Press, New York, 2003), pp. 37–44.

    Google Scholar 

  10. A. Bostan, E. Schost, Polynomial evaluation and interpolation on special sets of points, J. Complexity 21(4), 420–446 (2005).

    Article  MATH  MathSciNet  Google Scholar 

  11. P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory. Grundlehren Math. Wiss., vol. 315 (Springer, Berlin, 1997).

    MATH  Google Scholar 

  12. A. Cafure, G. Matera, A. Waissbein, Inverting bijective polynomial maps over finite fields, in Proceedings of the 2006 Information Theory Workshop, ITW2006, Punta del Este, Uruguay, 13–17 March 2006, ed. by G. Seroussi, A. Viola (IEEE Information Theory Society, New York, 2006), pp. 27–31.

    Chapter  Google Scholar 

  13. D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo, The hardness of polynomial equation solving, Found. Comput. Math. 3(4), 347–420 (2003).

    Article  MATH  MathSciNet  Google Scholar 

  14. D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry. Grad. Texts in Math., vol. 185 (Springer, New York, 1998).

    MATH  Google Scholar 

  15. J.-P. Dedieu, Condition number analysis for sparse polynomial systems, in Foundations of Computational Mathematics, Rio de Janeiro, 1997, ed. by F. Cucker, M. Shub (Springer, Berlin, 1997), pp. 267–276.

    Google Scholar 

  16. C. Durvye, G. Lecerf, A concise proof of the Kronecker polynomial system solver from scratch, Exp. Math. (2006, in press). doi:10.1016/j.expmath.2007.07.001.

  17. I.Z. Emiris, J. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symb. Comput. 20, 117–149 (1995).

    Article  MATH  MathSciNet  Google Scholar 

  18. G. Ewald, Combinatorial Convexity and Algebraic Geometry. Grad. Texts in Math., vol. 168 (Springer, New York, 1996).

    MATH  Google Scholar 

  19. I.M. Gelfand, M.M. Kapranov, A.V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants (Birkhäuser, Boston, 1994).

    MATH  Google Scholar 

  20. M. Giusti, K. Hägele, J. Heintz, J.E. Morais, J.L. Montaña, L.M. Pardo, Lower bounds for Diophantine approximation, J. Pure Appl. Algebra 117–118, 277–317 (1997).

    Article  Google Scholar 

  21. M. Giusti, J. Heintz, J.E. Morais, J. Morgenstern, L.M. Pardo, Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124, 101–146 (1998).

    Article  MATH  MathSciNet  Google Scholar 

  22. M. Giusti, G. Lecerf, B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complex. 17(1), 154–211 (2001).

    Article  MATH  MathSciNet  Google Scholar 

  23. J. Heintz, On the computational complexity of polynomials and bilinear maps, in Proceedings of the 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-5, Menorca, Spain, 15–19 June 1987, ed. by L. Huguet, A. Poli. Lecture Notes in Comput. Sci., vol. 356 (Springer, Berlin, 1989), pp. 269–300.

    Google Scholar 

  24. J. Heintz, G. Jeronimo, J. Sabia, P. Solernó, Intersection theory and deformation algorithms. The multihomogeneous case, Manuscript, Universidad de Buenos Aires, 2002.

  25. J. Heintz, T. Krick, S. Puddu, J. Sabia, A. Waissbein, Deformation techniques for efficient polynomial equation solving, J. Complex. 16(1), 70–109 (2000).

    Article  MATH  MathSciNet  Google Scholar 

  26. B. Huber, B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comput. 64(212), 1541–1555 (1995).

    Article  MATH  MathSciNet  Google Scholar 

  27. B. Huber, B. Sturmfels, Bernstein’s theorem in affine space, Discrete Comput. Geom. 17, 137–141 (1997).

    Article  MATH  MathSciNet  Google Scholar 

  28. G. Jeronimo, T. Krick, J. Sabia, M. Sombra, The computational complexity of the Chow form, Found. Comput. Math. 4(1), 41–117 (2004).

    Article  MATH  MathSciNet  Google Scholar 

  29. A.G. Khovanski, Newton polyhedra and the genus of complete intersections, Funct. Anal. Appl. 12, 38–46 (1978).

    Google Scholar 

  30. A.G. Kushnirenko, Newton polytopes and the Bézout theorem, Funct. Anal. Appl. 10, 233–235 (1976).

    Article  MATH  Google Scholar 

  31. G. Lecerf, Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math. 2(3), 247–293 (2002).

    Article  MATH  MathSciNet  Google Scholar 

  32. G. Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. Complex. 19(4), 564–596 (2003).

    Article  MathSciNet  Google Scholar 

  33. T.-Y. Li, X. Li, Finding mixed cells in the mixed volume computation, Found. Comput. Math. 1(2), 161–181 (2001).

    Article  MATH  MathSciNet  Google Scholar 

  34. T.Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numer. 6, 399–436 (1997).

    Article  Google Scholar 

  35. T.Y. Li, X. Wang, The BKK root count in ℂn, Math. Comput. 65(216), 1477–1484 (1996).

    Article  MATH  Google Scholar 

  36. G. Malajovich, J.M. Rojas, High probability analysis of the condition number of sparse polynomial systems, Theor. Comput. Sci. 315(2–3), 525–555 (2004).

    Article  MATH  MathSciNet  Google Scholar 

  37. A. Morgan, Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems (Prentice-Hall, Englewood Cliffs, 1987).

    MATH  Google Scholar 

  38. A. Morgan, A. Sommese, C. Wampler, A generic product–decomposition formula for Bézout numbers, SIAM J. Numer. Anal. 32, 1308–1325 (1995).

    Article  MATH  MathSciNet  Google Scholar 

  39. M. Oka, Non-Degenerate Complete Intersection Singularity (Hermann, Paris, 1997).

    MATH  Google Scholar 

  40. L.M. Pardo, How lower and upper complexity bounds meet in elimination theory, in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-11, ed. by G. Cohen, M. Giusti, T. Mora. Lecture Notes in Comput. Sci., vol. 948 (Springer, Berlin, 1995), pp. 33–69.

    Google Scholar 

  41. L.M. Pardo, J. San Martín, Deformation techniques to solve generalized Pham systems, Theoret. Comput. Sci. 315(2–3), 593–625 (2004).

    Article  MATH  MathSciNet  Google Scholar 

  42. P. Pedersen, B. Sturmfels, Product formulas for resultants and Chow forms, Math. Z. 214(3), 377–396 (1993).

    Article  MATH  MathSciNet  Google Scholar 

  43. P. Philippon, M. Sombra, Hauteur normalisée des variétés toriques projectives, J. Inst. Math. Jussieu (2003, in press). doi:10.1017/S1474748007000138, 35pp., eprint math.NT/0406476.

  44. P. Philippon, M. Sombra, Géométrie Diophantienne et variétés toriques, C. R. Math. Acad. Sci. Paris 340, 507–512 (2005).

    MATH  MathSciNet  Google Scholar 

  45. P. Philippon, M. Sombra, A refinement of the Kušnirenko–Bernštein estimate, Manuscript, 2006. arXiv:0709.3306.

  46. J.M. Rojas, Solving degenerate sparse polynomial systems faster, J. Symbolic Comput. 28(1/2), 155–186 (1999).

    Article  MATH  MathSciNet  Google Scholar 

  47. J.M. Rojas, Algebraic geometry over four rings and the frontier of tractability, in Proceedings of a Conference on Hilbert’s Tenth Problem and Related Subjects, University of Gent, 1–5 November 1999, ed. by J. Denef et al. Contemp. Math., vol. 270 (AMS, Providence, 2000), pp. 275–321

    Google Scholar 

  48. J.M. Rojas, Why polyhedra matter in non-linear equation solving, in Proceedings of the Conference on Algebraic Geometry and Geometric Modelling, Vilnius, Lithuania, 29 July–2 August 2002. Contemp. Math., vol. 334 (AMS, Providence, 2003), pp. 293–320.

    Google Scholar 

  49. J.M. Rojas, X. Wang, Counting affine roots of polynomial systems via pointed Newton polytopes, J. Complex. 12(2), 116–133 (1996).

    Article  MATH  MathSciNet  Google Scholar 

  50. J. Sabia, P. Solernó, Bounds for traces in complete intersections and degrees in the Nullstellensatz, Appl. Algebra Eng. Commun. Comput. 6(6), 353–376 (1996).

    Article  Google Scholar 

  51. J.E. Savage, Models of Computation. Exploring the Power of Computing (Addison-Wesley, Reading, 1998).

    MATH  Google Scholar 

  52. E. Schost, Computing parametric geometric resolutions, Appl. Algebra Eng. Commun. Comput. 13, 349–393 (2003).

    Article  MathSciNet  Google Scholar 

  53. A. Sommese, C. Wampler, The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (World Scientific, Singapore, 2005).

    MATH  Google Scholar 

  54. A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH, Zürich, Switzerland, 2000.

  55. V. Strassen, Algebraic complexity theory, in Handbook of Theoretical Computer Science, ed. by J. van Leeuwen (Elsevier, Amsterdam, 1990), pp. 634–671.

    Google Scholar 

  56. J. Verschelde, K. Gatermann, R. Cools, Mixed volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom. 16(1), 69–112 (1996).

    Article  MATH  MathSciNet  Google Scholar 

  57. J. Verschelde, P. Verlinden, R. Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31(3), 915–930 (1994).

    Article  MATH  MathSciNet  Google Scholar 

  58. J. von zur Gathen, Parallel arithmetic computations: a survey, in Proceedings of the 12th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Czechoslovakia, 25–29 August 1986, ed. by J. Gruska, B. Rovan, J. Wiedermann. Lecture Notes in Comput. Sci., vol. 233 (Springer, Berlin, 1986), pp. 93–112.

    Google Scholar 

  59. J. von zur Gathen, J. Gerhard, Modern Computer Algebra (Cambridge University Press, Cambridge, 1999).

    MATH  Google Scholar 

  60. R.J. Walker, Algebraic Curves (Dover, New York, 1950).

    MATH  Google Scholar 

  61. R. Zippel, Effective Polynomial Computation. Kluwer Int. Ser. Eng. Comput. Sci., vol. 241 (Kluwer, Dordrecht, 1993).

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I, 1428, Buenos Aires, Argentina

    Gabriela Jeronimo & Pablo Solernó

  2. National Council of Science and Technology (CONICET), Buenos Aires, Argentina

    Gabriela Jeronimo, Guillermo Matera & Pablo Solernó

  3. Instituto de Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutiérrez 1150, 1613 Los Polvorines, Buenos Aires, Argentina

    Guillermo Matera

  4. CoreLabs, CORE Security Technologies, Humboldt 1967, C1414CTU, Buenos Aires, Argentina

    Ariel Waissbein

  5. Doctorado en Ingeniería, Instituto Tecnológico de Buenos Aires, Av. Eduardo Madero 399, C1106ACD, Buenos Aires, Argentina

    Ariel Waissbein

Authors
  1. Gabriela Jeronimo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guillermo Matera
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pablo Solernó
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ariel Waissbein
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gabriela Jeronimo.

Additional information

Communicated by Mike Shub.

Research was partially supported by the following grants: UBACyT X112 (2004–2007), UBACyT X847 (2006–2009), PIP CONICET 2461, PIP CONICET 5852/05, ANPCyT PICT 2005 17-33018, UNGS 30/3005, MTM2004-01167 (2004–2007), MTM2007-62799 and CIC 2007–2008.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jeronimo, G., Matera, G., Solernó, P. et al. Deformation Techniques for Sparse Systems. Found Comput Math 9, 1–50 (2009). https://doi.org/10.1007/s10208-008-9024-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-008-9024-2

Keywords

Mathematics Subject Classification (2000)

Search

Navigation