{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:27:10Z","timestamp":1773228430328,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s10208-013-9143-2","type":"journal-article","created":{"date-parts":[[2013,1,31]],"date-time":"2013-01-31T19:52:51Z","timestamp":1359661971000},"page":"253-295","source":"Crossref","is-referenced-by-count":39,"title":["Robust Certified Numerical Homotopy Tracking"],"prefix":"10.1007","volume":"13","author":[{"given":"Carlos","family":"Beltr\u00e1n","sequence":"first","affiliation":[]},{"given":"Anton","family":"Leykin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,2,1]]},"reference":[{"issue":"8","key":"9143_CR1","doi-asserted-by":"crossref","first-page":"1844","DOI":"10.1016\/j.jpaa.2010.10.016","volume":"215","author":"D.J. Bates","year":"2011","unstructured":"D.J. Bates, C. Peterson, A.J. Sommese, C.W. Wampler, Numerical computation of the genus of an irreducible curve within an algebraic set, J. Pure Appl. Algebra 215(8), 1844\u20131851 (2011).","journal-title":"J. Pure Appl. Algebra"},{"key":"9143_CR2","unstructured":"D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: software for numerical algebraic geometry. Available at http:\/\/www.nd.edu\/~sommese\/bertini ."},{"issue":"3","key":"9143_CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1983","unstructured":"W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci. 22(3), 317\u2013330 (1983).","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9143_CR4","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s00211-010-0334-3","volume":"117","author":"C. Beltr\u00e1n","year":"2011","unstructured":"C. Beltr\u00e1n, A\u00a0continuation method to solve polynomial systems, and its complexity, Numer. Math. 117(1), 89\u2013113 (2011).","journal-title":"Numer. Math."},{"issue":"1","key":"9143_CR5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1080\/10586458.2011.606184","volume":"21","author":"C. Beltr\u00e1n","year":"2012","unstructured":"C. Beltr\u00e1n, A. Leykin, Certified numerical homotopy tracking, Exp. Math. 21(1), 69\u201383 (2012).","journal-title":"Exp. Math."},{"issue":"1","key":"9143_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10208-005-0211-0","volume":"8","author":"C. Beltr\u00e1n","year":"2008","unstructured":"C. Beltr\u00e1n, L.M. Pardo, On Smale\u2019s 17th problem: a probabilistic positive solution, Found. Comput. Math. 8(1), 1\u201343 (2008).","journal-title":"Found. Comput. Math."},{"key":"9143_CR7","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1090\/S0894-0347-08-00630-9","volume":"22","author":"C. Beltr\u00e1n","year":"2009","unstructured":"C. Beltr\u00e1n, L.M. Pardo, Smale\u2019s 17th problem: average polynomial time to compute affine and projective solutions, J. Am. Math. Soc. 22, 363\u2013385 (2009).","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"9143_CR8","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10208-010-9078-9","volume":"11","author":"C. Beltr\u00e1n","year":"2011","unstructured":"C. Beltr\u00e1n, L.M. Pardo, Fast linear homotopy to find approximate zeros of polynomial systems, Found. Comput. Math. 11(1), 95\u2013129 (2011).","journal-title":"Found. Comput. Math."},{"key":"9143_CR9","series-title":"The IMA Vol. Math. Appl.","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-0-387-75155-9_3","volume-title":"Algorithms in Algebraic Geometry","author":"S. Billey","year":"2008","unstructured":"S. Billey, R. Vakil, Intersections of Schubert varieties and other permutation array schemes, in Algorithms in Algebraic Geometry, ed. by A. Dickenstein, F.O. Schreyer, A.J. Sommese. The IMA Vol. Math. Appl., vol.\u00a0146 (Springer, New York, 2008), pp.\u00a021\u201354."},{"key":"9143_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers; NP completeness, recursive functions and universal machines, Bull. Am. Math. Soc. 21, 1\u201346 (1989).","journal-title":"Bull. Am. Math. Soc."},{"key":"9143_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1998)."},{"key":"9143_CR12","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.4007\/annals.2011.174.3.8","volume":"174","author":"P. B\u00fcrguisser","year":"2011","unstructured":"P. B\u00fcrguisser, F. Cucker, On a problem posed by Steve Smale, Ann. Math. 174, 1785\u20131836 (2011).","journal-title":"Ann. Math."},{"issue":"1","key":"9143_CR13","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/jcom.2000.0572","volume":"17","author":"D. Castro","year":"2001","unstructured":"D. Castro, K. H\u00e4gele, J.E. Morais, L.M. Pardo, Kronecker\u2019s and Newton\u2019s approaches to solving: a first comparison, J. Complex. 17(1), 212\u2013303 (2001).","journal-title":"J. Complex."},{"issue":"1","key":"9143_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s002080010017","volume":"2","author":"D. Castro","year":"2002","unstructured":"D. Castro, J.L. Monta\u00f1a, L.M. Pardo, J. San Mart\u00edn, The distribution of condition numbers of rational data of bounded bit length, Found. Comput. Math. 2(1), 1\u201352 (2002).","journal-title":"Found. Comput. Math."},{"key":"9143_CR15","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (MIT Press, Cambridge, 1990)."},{"key":"9143_CR16","author":"J.-P. Dedieu","year":"2010","unstructured":"J.-P. Dedieu, G. Malajovich, M. Shub, Adaptative step size selection for homotopy methods to solve polynomial equations, IMA J. Numer. Anal. (2010). doi: 10.1093\/imanum\/drs007 .","journal-title":"IMA J. Numer. Anal."},{"issue":"1","key":"9143_CR17","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01459082","volume":"40","author":"J.D. Dixon","year":"1982","unstructured":"J.D. Dixon, Exact solution of linear equations using p-adic expansions, Numer. Math. 40(1), 137\u2013141 (1982).","journal-title":"Numer. Math."},{"key":"9143_CR18","unstructured":"D.R. Grayson, M.E. Stillman, Macaulay 2, a software system for research in algebraic geometry. Available at http:\/\/www.math.uiuc.edu\/Macaulay2\/ ."},{"key":"9143_CR19","unstructured":"J.D. Hauenstein, F. Sottile, alphacertified: certifying solutions to polynomial systems (2010). arXiv:1011.1091v1 ."},{"issue":"3","key":"9143_CR20","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/0731048","volume":"31","author":"R.B. Kearfott","year":"1994","unstructured":"R.B. Kearfott, Z. Xing, An interval step control for continuation methods, SIAM J. Numer. Anal. 31(3), 892\u2013914 (1994).","journal-title":"SIAM J. Numer. Anal."},{"key":"9143_CR21","unstructured":"M.H. Kim, Computational complexity of the Euler type algorithms for the roots of complex polynomials. Ph.D. Thesis, The City University of New York, 1985."},{"key":"9143_CR22","unstructured":"T.L. Lee, T.Y. Li, C.H. Tsai, Hom4ps-2.0: A\u00a0software package for solving polynomial systems by the polyhedral homotopy continuation method. Available at. http:\/\/hom4ps.math.msu.edu\/HOM4PS_soft.htm ."},{"key":"9143_CR23","doi-asserted-by":"crossref","first-page":"5","DOI":"10.2140\/jsag.2011.3.5","volume":"3","author":"A. Leykin","year":"2011","unstructured":"A. Leykin, Numerical algebraic geometry for Macaulay2, J. Softw. Algebr. Geom. 3, 5\u201310 (2011).","journal-title":"J. Softw. Algebr. Geom."},{"issue":"267","key":"9143_CR24","doi-asserted-by":"crossref","first-page":"1749","DOI":"10.1090\/S0025-5718-09-02239-X","volume":"78","author":"A. Leykin","year":"2009","unstructured":"A. Leykin, F. Sottile, Galois groups of Schubert problems via homotopy computation, Math. Comput. 78(267), 1749\u20131765 (2009).","journal-title":"Math. Comput."},{"key":"9143_CR25","unstructured":"G. Malajovich, On the complexity of path-following Newton algorithms for solving systems of polynomial equations with integer coefficients. Ph.D. Thesis, Univ. California, Berkley, 1993."},{"key":"9143_CR26","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0304-3975(94)00065-4","volume":"133","author":"G. Malajovich","year":"1994","unstructured":"G. Malajovich, On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theor. Comput. Sci. 133, 65\u201384 (1994).","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9143_CR27","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1006\/jcom.2000.0552","volume":"16","author":"G. Malajovich","year":"2000","unstructured":"G. Malajovich, Condition number bounds for problems with integer coefficients, J. Complex. 16(3), 529\u2013551 (2000).","journal-title":"J. Complex."},{"key":"9143_CR28","unstructured":"G. Malajovich, PSS\u2014Polynomial System Solver version 3.0.5. Available at. http:\/\/www.labma.ufrj.br\/~gregorio\/software.php ."},{"key":"9143_CR29","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, 1994)."},{"key":"9143_CR30","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/978-1-4612-2740-3_40","volume-title":"From Topology to Computation: Proceedings of the Smalefest","author":"M. Shub","year":"1993","unstructured":"M. Shub, Some remarks on Bezout\u2019s theorem and complexity theory, in From Topology to Computation: Proceedings of the Smalefest, ed. by M.W. Hirsch, J.E. Marsden, M. Shub (Springer, New York, 1993), pp.\u00a0443\u2013455."},{"issue":"2","key":"9143_CR31","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s10208-007-9017-6","volume":"9","author":"M. Shub","year":"2009","unstructured":"M. Shub, Complexity of B\u00e9zout\u2019s theorem. VI: Geodesics in the condition (number) metric, Found. Comput. Math. 9(2), 171\u2013178 (2009).","journal-title":"Found. Comput. Math."},{"key":"9143_CR32","series-title":"Progr. Math.","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/978-1-4612-2752-6_19","volume-title":"Computational Algebraic Geometry","author":"M. Shub","year":"1993","unstructured":"M. Shub, S. Smale, Complexity of B\u00e9zout\u2019s theorem. II. Volumes and probabilities, in Computational Algebraic Geometry, ed. by Fr. Eyssette, A. Galligo. Progr. Math., vol.\u00a0109 (Birkh\u00e4user, Boston, 1993), pp.\u00a0267\u2013285."},{"issue":"2","key":"9143_CR33","first-page":"459","volume":"6","author":"M. Shub","year":"1993","unstructured":"M. Shub, S. Smale, Complexity of B\u00e9zout\u2019s theorem. I. Geometric aspects, J. Am. Math. Soc. 6(2), 459\u2013501 (1993).","journal-title":"J. Am. Math. Soc."},{"key":"9143_CR34","series-title":"Theoret. Comput. Sci.","first-page":"141","volume-title":"Selected Papers of the Workshop on Continuous Algorithms and Complexity","author":"M. Shub","year":"1994","unstructured":"M. Shub, S. Smale, Complexity of Bezout\u2019s theorem. V. Polynomial time, in Selected Papers of the Workshop on Continuous Algorithms and Complexity, Barcelona, 1993. Theoret. Comput. Sci., vol.\u00a0133 (1994), pp.\u00a0141\u2013164."},{"issue":"1","key":"9143_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","volume":"4","author":"S. Smale","year":"1981","unstructured":"S. Smale, The fundamental theorem of algebra and complexity theory, Bull. Am. Math. Soc. 4(1), 1\u201336 (1981).","journal-title":"Bull. Am. Math. Soc."},{"key":"9143_CR36","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/978-1-4612-4984-9_13","volume-title":"The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics","author":"S. Smale","year":"1986","unstructured":"S. Smale, Newton\u2019s method estimates from data at one point, in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (Springer, New York, 1986), pp.\u00a0185\u2013196."},{"key":"9143_CR37","unstructured":"J. van der Hoeven, Reliable homotopy continuation. Technical Report, HAL 00589948 (2011)."},{"issue":"2","key":"9143_CR38","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/317275.317286","volume":"25","author":"J. Verschelde","year":"1999","unstructured":"J. Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw. 25(2), 251\u2013276 (1999). Available at http:\/\/www.math.uic.edu\/~jan .","journal-title":"ACM Trans. Math. Softw."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-013-9143-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-013-9143-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-013-9143-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T11:05:12Z","timestamp":1559127912000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-013-9143-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,1]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9143"],"URL":"https:\/\/doi.org\/10.1007\/s10208-013-9143-2","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,1]]}}}