Smale’s 17th problem: advances and open directions. (English) Zbl 07402068
Summary: We give an overview of Smale’s 17th problem describing the context in which Smale proposed it, the ideas that led to its solution, and the extensions and subsequent progress after this solution.
MSC:
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
| 65Y20 | Complexity and performance of numerical algorithms |
| 14-XX | Algebraic geometry |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | N.H. Abel. Mémoire sur leséquations algébriques, ou l’on démontre l’impossibilité de la résolution de l’équation générale du cinquième degré. In L. Sylow and S. Lie, editors, OEuvres Complètes de Niels Henrik Abel, volume I, pages 28-33. Grøndahl & Søn, 1881. |
| [2] | D. Armentano, C. Beltrán, P. Bürgisser, F. Cucker, and M. Shub. Condition length and complexity for the solution of polynomial systems. Found. Comput. Math., 16:1401-1422, 2016. · Zbl 1358.65031 |
| [3] | D. Armentano, C. Beltrán, P. Bürgisser, F. Cucker, and M. Shub. A stable, polynomial-time algorithm for the eigenpair problem. J. Europ. Math. Soc., 20:1375-1437, 2018. · Zbl 1401.65034 |
| [4] | V. Arnold, M. Atiyah, P. Lax, and B. Mazur, editors. Mathematics: Frontiers and Perspectives. AMS, 2000. · Zbl 1047.00015 |
| [5] | W. Baur and V. Strassen. The complexity of partial derivatives. Theoret. Com-put. Sci., 22(3):317-330, 1983. · Zbl 0498.68028 |
| [6] | C. Beltrán, U. Etayo, J. Marzo, and J. Ortega-Cerdá. A sequence of polyno-mials with optimal condition number. J. Amer. Math. Soc., 34:219-244, 2021. · Zbl 1458.65164 |
| [7] | C. Beltrán and L.M. Pardo. On Smale’s 17 problem: a probabilistic positive solution. Found. Comput. Math., 8:1-43, 2008. · Zbl 1153.65048 |
| [8] | C. Beltrán and L.M. Pardo. Fast linear homotopy to find approximate zeros of polynomial systems. Found. Comput. Math., 11(1):95-129, 2011. · Zbl 1232.65075 |
| [9] | P. Bürgisser and F. Cucker. On a problem posed by Steve Smale. Annals of Mathematics, 174:1785-1836, 2011. · Zbl 1248.65047 |
| [10] | P. Bürgisser and F. Cucker. Condition, volume 349 of Grundlehren der math-ematischen Wissenschaften. Springer-Verlag, Berlin, 2013. · Zbl 1280.65041 |
| [11] | P. Bürgisser, F. Cucker, and P. Lairez. Rigid continuation paths II. Structured polynomial systems. Preprint. Available at arXiv:2010.10997, 2021. |
| [12] | J.W. Demmel. Applied Numerical Linear Algebra. SIAM, 1997. · Zbl 0879.65017 |
| [13] | J. Friberg. A geometric algorithm with solutions to quadratic equations in a sumerian juridical document from Ur III Umma. Cuneiform Digital Library Journal, 3, 2009. |
| [14] | V. Jones. Ten problems. In [4], pg. 79-91. · Zbl 0969.57001 |
| [15] | E. Lahaye. Une méthode de resolution d’une categorie d’equations transcen-dantes. C. R. Acad. Sci. Paris, 198:1840-1842, 1934. · JFM 60.0259.03 |
| [16] | P. Lairez. A deterministic algorithm to compute approximate roots of polyno-mial systems in polynomial average time. Found. Comput. Math., 17(5):1265-1292, 2017. · Zbl 1458.65058 |
| [17] | P. Lairez. Rigid continuation paths I. Quasilinear average complexity for solv-ing polynomial systems. J. Amer. Math. Soc., 33(2):487-526, 2020. · Zbl 07179136 |
| [18] | G. Malajovich. Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric. Found. Comput. Math., 19(1):1-53, 2019. · Zbl 1408.65032 |
| [19] | G. Malajovich. Complexity of sparse polynomial solving 2: renormalization. Preprint. Available at arXiv:2005.01223, 2020. |
| [20] | N. Nisan. Lower bounds for non-commutative computation. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 410-418. ACM, 1991. |
| [21] | M. Shub. Complexity of Bézout’s Theorem VI geodesics in the condition (num-ber) metric. Found. Comput. Math., 9:171-178, 2009. · Zbl 1175.65060 |
| [22] | M. Shub and S. Smale. Complexity of Bézout’s Theorem I: geometric aspects. J. Amer. Math. Soc., 6:459-501, 1993. · Zbl 0821.65035 |
| [23] | M. Shub and S. Smale. Complexity of Bézout’s Theorem II: volumes and prob-abilities. In F. Eyssette and A. Galligo, editors, Computational Algebraic Ge-ometry, volume 109 of Progress in Mathematics, pages 267-285. Birkhäuser, 1993. · Zbl 0851.65031 |
| [24] | M. Shub and S. Smale. Complexity of Bézout’s Theorem III: condition number and packing. Journal of Complexity, 9:4-14, 1993. · Zbl 0846.65018 |
| [25] | M. Shub and S. Smale. Complexity of Bézout’s Theorem V: polynomial time. Theor. Comput. Sci., 133:141-164, 1994. · Zbl 0846.65022 |
| [26] | M. Shub and S. Smale. Complexity of Bézout’s Theorem IV: probability of success; extensions. SIAM J. of Numer. Anal., 33:128-148, 1996. · Zbl 0843.65035 |
| [27] | S. Smale. Mathematical problems for the next century. In [4], pg. 271-294. · Zbl 1031.00005 |
| [28] | S. Smale. Newton’s method estimates from data at one point. In R. Ewing, K. Gross, and C. Martin, editors, The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. Springer-Verlag, 1986. · Zbl 0613.65058 |
| [29] | S. Smale. Mathematical problems for the next century. Mathematical Intelli-gencer, 20:7-15, 1998. · Zbl 0947.01011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
