{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:43:22Z","timestamp":1776797002421,"version":"3.51.2"},"reference-count":21,"publisher":"American Mathematical Society (AMS)","issue":"287","license":[{"start":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T00:00:00Z","timestamp":1410307200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>A solution for Smale\u2019s 17th problem, for the case of systems with bounded degree was recently given. This solution, an algorithm computing approximate zeros of complex polynomial systems in average polynomial time, assumed infinite precision. In this paper we describe a finite-precision version of this algorithm. Our main result shows that this version works within the same time bounds and requires a precision which, on the average, amounts to a polynomial amount of bits in the mantissa of the intervening floating-point numbers.<\/p>","DOI":"10.1090\/s0025-5718-2013-02765-2","type":"journal-article","created":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T04:57:05Z","timestamp":1378875425000},"page":"1279-1317","source":"Crossref","is-referenced-by-count":4,"title":["Fast computation of zeros of polynomial systems with bounded degree under finite-precision"],"prefix":"10.1090","volume":"83","author":[{"given":"Ir\u00e9n\u00e9e","family":"Briquel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"Pe\u00f1a","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vera","family":"Roshchina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2013,9,10]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","article-title":"The complexity of partial derivatives","volume":"22","author":"Baur, Walter","year":"1983","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1080\/10586458.2011.606184","article-title":"Certified numerical homotopy tracking","volume":"21","author":"Beltr\u00e1n, Carlos","year":"2012","journal-title":"Exp. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10208-005-0211-0","article-title":"On Smale\u2019s 17th problem: a probabilistic positive solution","volume":"8","author":"Beltr\u00e1n, Carlos","year":"2008","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1090\/S0894-0347-08-00630-9","article-title":"Smale\u2019s 17th problem: average polynomial time to compute affine and projective solutions","volume":"22","author":"Beltr\u00e1n, Carlos","year":"2009","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10208-010-9078-9","article-title":"Fast linear homotopy to find approximate zeros of polynomial systems","volume":"11","author":"Beltr\u00e1n, Carlos","year":"2011","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484","volume-title":"Numerical methods for least squares problems","author":"Bj\u00f6rck, \u00c5ke","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0898713609"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and real computation","author":"Blum, Lenore","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0387982817"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.4007\/annals.2011.174.3.8","article-title":"On a problem posed by Steve Smale","volume":"174","author":"B\u00fcrgisser, Peter","year":"2011","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"5-6","key":"9","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.jco.2008.03.001","article-title":"A numerical algorithm for zero counting. I. Complexity and accuracy","volume":"24","author":"Cucker, Felipe","year":"2008","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/300515.300519","article-title":"Complexity estimates depending on condition and round-off error","volume":"46","author":"Cucker, Felipe","year":"1999","journal-title":"J. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"11","series-title":"Johns Hopkins Studies in the Mathematical Sciences","isbn-type":"print","volume-title":"Matrix computations","author":"Golub, Gene H.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/080185413X","edition":"3"},{"key":"12","isbn-type":"print","volume-title":"Accuracy and stability of numerical algorithms","author":"Higham, Nicholas J.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0898713552"},{"key":"13","isbn-type":"print","first-page":"443","article-title":"Some remarks on Bezout\u2019s theorem and complexity theory","author":"Shub, Michael","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0387979328"},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s10208-007-9017-6","article-title":"Complexity of Bezout\u2019s theorem. VI. Geodesics in the condition (number) metric","volume":"9","author":"Shub, Michael","year":"2009","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"2","key":"15","doi-asserted-by":"publisher","first-page":"459","DOI":"10.2307\/2152805","article-title":"Complexity of B\u00e9zout\u2019s theorem. I. Geometric aspects","volume":"6","author":"Shub, Michael","year":"1993","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-1-4612-2752-6_19","article-title":"Complexity of Bezout\u2019s theorem. II. Volumes and probabilities","author":"Shub, M.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0817636781"},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1993.1002","article-title":"Complexity of Bezout\u2019s theorem. III. Condition number and packing","volume":"9","author":"Shub, Michael","year":"1993","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","article-title":"Complexity of Bezout\u2019s theorem. V. Polynomial time","volume":"133","author":"Shub, M.","year":"1994","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"1","key":"19","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0733008","article-title":"Complexity of Bezout\u2019s theorem. IV. Probability of success; extensions","volume":"33","author":"Shub, Michael","year":"1996","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"20","isbn-type":"print","first-page":"185","article-title":"Newton\u2019s method estimates from data at one point","author":"Smale, Steve","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387964142"},{"key":"21","isbn-type":"print","first-page":"271","article-title":"Mathematical problems for the next century","author":"Smale, Steve","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0821820702"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02765-2\/S0025-5718-2013-02765-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02765-2\/S0025-5718-2013-02765-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:53:43Z","timestamp":1776794023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02765-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,10]]},"references-count":21,"journal-issue":{"issue":"287","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["S0025-5718-2013-02765-2"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2013-02765-2","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9,10]]}}}