Condition Length and Complexity for the Solution of Polynomial Systems | Foundations of Computational Mathematics Skip to main content
Springer Nature Link
Log in

Condition Length and Complexity for the Solution of Polynomial Systems

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

Abstract

Smale’s 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale in Mathematical problems for the next century, American Mathematical Society, Providence, 2000). The main progress on Smale’s problem is Beltrán and Pardo (Found Comput Math 11(1):95–129, 2011) and Bürgisser and Cucker (Ann Math 174(3):1785–1836, 2011). In this paper, we will improve on both approaches and prove an interesting intermediate result on the average value of the condition number. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán and Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser and Cucker (2011), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last theorem is similar to the main result of Bürgisser and Cucker (2011) but relies only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser and Cucker (2011). We build on methods developed in Armentano et al. (2014).

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. In [16], the theorem is actually proven in the projective space instead of the sphere, which is sharper, but we only use the sphere version in this paper.

References

  1. D. Armentano. Stochastic perturbation and smooth condition numbers. Journal of Complexity 26 (2010) 161–171.

    Article  MathSciNet  MATH  Google Scholar 

  2. D. Armentano, C. Beltrán, P. Bürgisser, F. Cucker, M. Shub. A stable, polynomial-time algorithm for the eigenpair problem (2015). Preprint, available at arXiv:1410.0116.

  3. C. Beltrán. A continuation method to solve polynomial systems and its complexity. Numer. Math. 117 (2011), no. 1, 89–113.

    Article  MathSciNet  MATH  Google Scholar 

  4. C. Beltrán and A. Leykin. Robust certified numerical homotopy tracking. Found. Comput. Math., 13(2):253–295, 2013.

    Article  MathSciNet  MATH  Google Scholar 

  5. C. Beltrán and L. M. Pardo. Smale’s 17th problem: average polynomial time to compute affine and projective solutions. J. Amer. Math. Soc. 22 (2009), no. 2, 363–385.

    Article  MathSciNet  MATH  Google Scholar 

  6. C. Beltrán and L. M. Pardo. Fast linear homotopy to find approximate zeros of polynomial systems. Found. Comput. Math. 11 (2011), no. 1, 95–129.

    Article  MathSciNet  MATH  Google Scholar 

  7. C. Beltrán, M. Shub. The complexity and geometry of numerically solving polynomial systems. Contemporary Mathematics, volume 604, 2013, pp. 71–104.

    Article  MathSciNet  MATH  Google Scholar 

  8. C. Beltrán, M. Shub. On the Geometry and Topology of the Solution Variety for Polynomial System Solving. Found. Comput. Math. 12 (2012), 719–763.

    Article  MathSciNet  MATH  Google Scholar 

  9. L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and real computation, Springer-Verlag, New York, 1998.

    Book  MATH  Google Scholar 

  10. P. Bürgisser and F. Cucker. On a problem posed by Steve Smale, Ann. of Math. (2) 174 (2011), no. 3, 1785–1836.

  11. P. Bürgisser, M. Clausen and A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften, Springer-Verlag, Berlin, 1996.

  12. P. Bürgisser and F. Cucker. Condition, volume 349 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 2013.

  13. K.P. Choi. On the medians of gamma distributions and an equation of Ramanujan, Proc. Amer. Math. Soc. 121 (1994), no. 1, 245–251.

    Article  MathSciNet  MATH  Google Scholar 

  14. J-P. Dedieu, G. Malajovich, and M. Shub. Adaptative step size selection for homotopy methods to solve polynomial equations. IMA Journal of Numerical Analysis 33 (2013), no. 1, 1–29.

    Article  MathSciNet  MATH  Google Scholar 

  15. P. Lairez. A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time. Preprint, available at arXiv:1507.05485.

  16. M. Shub. Complexity of Bezout’s theorem. VI. Geodesics in the condition (number) metric. Found. Comput. Math. 9 (2009), no. 2, 171–178.

    Article  MathSciNet  MATH  Google Scholar 

  17. M. Shub. Some remarks on Bezout’s theorem and complexity theory. In From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990), 443–455, Springer, New York, 1993.

  18. M. Shub and S. Smale. Complexity of Bézout’s theorem. I. Geometric aspects. J. Amer. Math. Soc. 6 (1993), no. 2, 459-501.

    MathSciNet  MATH  Google Scholar 

  19. M. Shub and S. Smale. Complexity of Bézout’s theorem. II: volumes and probabilities. Computational Algebraic Geometry. Progress in Mathematics Volume 109, 1993, pp 267–285

  20. M. Shub and S. Smale. Complexity of Bézout’s theorem. V: Polynomial time. Theoretical Computing Science, Vol 133, 1994, pag 141–164.

    Article  MathSciNet  MATH  Google Scholar 

  21. S. Smale. Mathematical problems for the next century, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271–294.

Download references

Author information

Authors and Affiliations

  1. Universidad de La República, Montevideo, Uruguay

    Diego Armentano

  2. Universidad de Cantabria, Santander, Spain

    Carlos Beltrán

  3. Technische Universität Berlin, Berlin, Germany

    Peter Bürgisser

  4. City University of Hong Kong, Kowloon Tong, Hong Kong

    Felipe Cucker

  5. City University of New York, New York, NY, USA

    Michael Shub

Authors
  1. Diego Armentano
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Carlos Beltrán
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Peter Bürgisser
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Felipe Cucker
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Michael Shub
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Michael Shub.

Additional information

Communicated by Teresa Krick.

Diego Armentano partially supported by Agencia Nacional de Investigación e Innovación (ANII), Uruguay, and by CSIC group 618. Carlos Beltrán partially suported by the research projects MTM2010-16051 and MTM2014-57590-P from Spanish Ministry of Science MICINN. Peter Bürgisser partially funded by DFG Research Grant BU 1371/2-2. Felipe Cucker partially funded by a GRF Grant from the Research Grants Council of the Hong Kong SAR (Project Number CityU 100813).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Armentano, D., Beltrán, C., Bürgisser, P. et al. Condition Length and Complexity for the Solution of Polynomial Systems. Found Comput Math 16, 1401–1422 (2016). https://doi.org/10.1007/s10208-016-9309-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-016-9309-9

Keywords

Mathematics Subject Classification