{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:14:34Z","timestamp":1743153274976,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662242"},{"type":"electronic","value":"9783540485230"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_5","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"55-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Real Computations with Fake Numbers"],"prefix":"10.1007","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S. Basu","year":"1996","unstructured":"S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM, 43:1002\u20131045, 1996.","journal-title":"Journal of the ACM"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 21:1\u201346, 1989.","journal-title":"Bulletin of the Amer. Math. Soc."},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen, and A. Shokrollahi. Algebraic Complexity Theory. Springer-Verlag, 1996.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/0885-064X(92)90024-6","volume":"8","author":"F. Cucker","year":"1992","unstructured":"F. Cucker. PIR \u2260 NCIR. Journal of Complexity, 8:230\u2013238, 1992.","journal-title":"Journal of Complexity"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"F. Cucker and S. Smale. Complexity estimates depending on condition and round-off error. To appear in Journal of the ACM, 1997.","DOI":"10.1007\/3-540-68530-8_10"},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01394453","volume":"28","author":"L.S. de Jong","year":"1977","unstructured":"L.S. de Jong. Towards a formal definition of numerical stability. Numer. Math., 28:211\u2013219, 1977.","journal-title":"Numer. Math."},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"J.W. Demmel. Applied Numerical Linear Algebra. SIAM, 1997.","DOI":"10.1137\/1.9781611971446"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF02288367","volume":"1","author":"C. Eckart","year":"1936","unstructured":"C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1:211\u2013218, 1936.","journal-title":"Psychometrika"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"H.H. Goldstine. A History of Numerical Analysis from the 16th through the 19th Century. Springer-Verlag, 1977.","DOI":"10.1007\/978-1-4684-9472-3"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"101","DOI":"10.24033\/bsmf.2138","volume":"118","author":"J. Heintz","year":"1990","unstructured":"J. Heintz, M.-F. Roy, and P. Solerno. FrSur la complexit\u00e9 du principe de Tarski-Seidenberg. Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France, 118:101\u2013126, 1990.","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"5_CR12","unstructured":"N. Higham. Accuracy and Stability of Numerical Algorithms. SIAM, 1996."},{"key":"5_CR13","unstructured":"D. Knuth. The Art of Computer Programming, volume 2, Seminumerical Algorithms. Addison-Wesley, 2 edition, 1981."},{"key":"5_CR14","unstructured":"P. Koiran. The real dimension problem is NPIR-complete. To appear in Journal of Complexity, 1997."},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"A.M. Ostrowski. On two problems in abstract algebra connected with Horner\u2019s rule. In Studies in Mathematics and Mechanics presented to Richard von Mises, pages 40\u201348. Academic Press, 1954.","DOI":"10.1016\/B978-1-4832-3272-0.50010-7"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1070\/RM1966v021n01ABEH004147","volume":"21","author":"V. Y. Pan","year":"1966","unstructured":"V. Ya. Pan. Methods of computing values of polynomials. Russian Math. Surveys, 21:105\u2013136, 1966.","journal-title":"Russian Math. Surveys"},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I. Journal of Symbolic Computation, 13:255\u2013299, 1992.","journal-title":"Journal of Symbolic Computation"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01581690","volume":"65","author":"J. Renegar","year":"1994","unstructured":"J. Renegar. Some perturbation theory for linear programming. Mathematical Programming, 65:73\u201391, 1994.","journal-title":"Mathematical Programming"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1137\/0805026","volume":"5","author":"J. Renegar","year":"1995","unstructured":"J. Renegar. Incorporating condition measures into the complexity theory of linear programming. SIAM Journal of Optimization, 5:506\u2013524, 1995.","journal-title":"SIAM Journal of Optimization"},{"key":"5_CR20","first-page":"279","volume":"70","author":"J. Renegar","year":"1995","unstructured":"J. Renegar. Linear programming, complexity theory and elementary functional analysis. Mathematical Programming, 70:279\u2013351, 1995.","journal-title":"Mathematical Programming"},{"key":"5_CR21","first-page":"459","volume":"6","author":"M. Shub","year":"1993","unstructured":"M. Shub and S. Smale. Complexity of Bezout\u2019s theorem I: geometric aspects. Journal of the Amer. Math. Soc., 6:459\u2013501, 1993.","journal-title":"Journal of the Amer. Math. Soc."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"M. Shub and S. Smale. Complexity of Bezout\u2019s theorem II: volumes and probabilities. In F. Eyssette and A. Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267\u2013285. Birkh\u00e4user, 1993.","DOI":"10.1007\/978-1-4612-2752-6_19"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1993.1002","volume":"9","author":"M. Shub","year":"1993","unstructured":"M. Shub and S. Smale. Complexity of Bezout\u2019s theorem III: condition number and packing. Journal of Complexity, 9:4\u201314, 1993.","journal-title":"Journal of Complexity"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","volume":"133","author":"M. Shub","year":"1994","unstructured":"M. Shub and S. Smale. Complexity of Bezout\u2019s theorem V: polynomial time. Theoretical Computer Science, 133:141\u2013164, 1994.","journal-title":"Theoretical Computer Science"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0733008","volume":"33","author":"M. Shub","year":"1996","unstructured":"M. Shub and S. Smale. Complexity of Bezout\u2019s theorem IV: probability of success; extensions. SIAM J. of Numer. Anal., 33:128\u2013148, 1996.","journal-title":"SIAM J. of Numer. Anal."},{"key":"5_CR26","doi-asserted-by":"publisher","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. Bulletin of the Amer. Math. Soc., 4:1\u201336, 1981.","journal-title":"Bulletin of the Amer. Math. Soc."},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/1032043","volume":"32","author":"S. Smale","year":"1990","unstructured":"S. Smale. Some remarks on the foundations of numerical analysis. SIAM Review, 32:211\u2013220, 1990.","journal-title":"SIAM Review"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"S. Smale. Complexity theory and numerical analysis. In A. Iserles, editor, Acta Numerica, pages 523\u2013551. Cambridge University Press, 1997.","DOI":"10.1017\/S0962492900002774"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"L.N. Trefethen and D. Bau III. Numerical Linear Algebra. SIAM, 1997.","DOI":"10.1137\/1.9780898719574"},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1137\/0611023","volume":"11","author":"L.N. Trefethen","year":"1990","unstructured":"L.N. Trefethen and R.S. Schreiber. Average-case stability of Gaussian elimination. SIAM J. Matrix Anal. Appl., 11:335\u2013360, 1990.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"5_CR31","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0885-064X(90)90004-W","volume":"6","author":"E. Triesch","year":"1990","unstructured":"E. Triesch. A note on a theorem of Blum, Shub, and Smale. Journal of Complexity, 6:166\u2013169, 1990.","journal-title":"Journal of Complexity"},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","volume":"1","author":"A.M. Turing","year":"1948","unstructured":"A.M. Turing. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math., 1:287\u2013308, 1948.","journal-title":"Quart. J. Mech. Appl. Math."},{"key":"5_CR33","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1090\/S0002-9904-1947-08909-6","volume":"53","author":"J. von Neumann","year":"1947","unstructured":"J. von Neumann and H.H. Goldstine. Numerical inverting matrices of high order. Bulletin of the Amer. Math. Soc., 53:1021\u20131099, 1947.","journal-title":"Bulletin of the Amer. Math. Soc."},{"key":"5_CR34","unstructured":"J. Wilkinson. Rounding Errors in Algebraic Processes. Prentice Hall, 1963."},{"key":"5_CR35","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1137\/1013095","volume":"13","author":"J. Wilkinson","year":"1971","unstructured":"J. Wilkinson. Modern error analyis. SIAM Review, 13:548\u2013568, 1971.","journal-title":"SIAM Review"},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF01399601","volume":"27","author":"H. Wo\u017aniakowski","year":"1977","unstructured":"H. Wo\u017aniakowski. Numerical stability for solving non-linear equations. Numer. Math., 27:373\u2013390, 1977.","journal-title":"Numer. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T03:03:55Z","timestamp":1642820635000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}