{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T10:40:12Z","timestamp":1738320012340,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540855200"},{"type":"electronic","value":"9783540855217"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85521-7_4","type":"book-chapter","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T06:45:26Z","timestamp":1217918726000},"page":"57-82","source":"Crossref","is-referenced-by-count":14,"title":["Real Algebraic Numbers: Complexity Analysis and Experimentation"],"prefix":"10.1007","author":[{"given":"Ioannis Z.","family":"Emiris","sequence":"first","affiliation":[]},{"given":"Bernard","family":"Mourrain","sequence":"additional","affiliation":[]},{"given":"Elias P.","family":"Tsigaridas","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01395988","volume":"36","author":"A. Akritas","year":"1980","unstructured":"Akritas, A.: An implementation of Vincent\u2019s theorem. Numerische Mathematik\u00a036, 53\u201362 (1980)","journal-title":"Numerische Mathematik"},{"key":"4_CR2","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05355-3","volume-title":"Algorithms in Real Algebraic Geometry","author":"S. Basu","year":"2003","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol.\u00a010. Springer, Heidelberg (2003)"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0022-0000(86)90029-2","volume":"32","author":"M. Ben-Or","year":"1986","unstructured":"Ben-Or, M., Kozen, D., Reif, J.H.: The complexity of elementary algebra and geometry. J. Comput. Syst. Sci.\u00a032, 251\u2013264 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/11561071_16","volume-title":"Algorithms \u2013 ESA 2005","author":"E. Berberich","year":"2005","unstructured":"Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Kettner, L., Mehlhorn, K., Reichel, J., Schmitt, S., Sch\u00f6mer, E., Wolpert, N.: EXACUS: Efficient and Exact Algorithms for Curves and Surfaces. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 155\u2013166. Springer, Heidelberg (2005)"},{"issue":"3\u20134","key":"4_CR5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF02207694","volume":"13","author":"D. Bini","year":"1996","unstructured":"Bini, D.: Numerical computation of polynomial zeros by means of Aberth\u2019s method. Numerical Algorithms\u00a013(3\u20134), 179\u2013200 (1996)","journal-title":"Numerical Algorithms"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Bini, D., Fiorentino, G.: Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numerical Algorithms, 127\u2013173 (2000)","DOI":"10.1023\/A:1019199917103"},{"issue":"5","key":"4_CR7","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1093\/comjnl\/36.5.409","volume":"36","author":"J. Canny","year":"1993","unstructured":"Canny, J.: Improved algorithms for sign determination and existential quantifier elimination. The Computer Journal\u00a036(5), 409\u2013418 (1993)","journal-title":"The Computer Journal"},{"key":"4_CR8","unstructured":"Cazals, F., Faug\u00e8re, J.-C., Pouget, M., Rouillier, F.: The implicit structure of ridges of a smooth parametric surface. Technical Report 5608, INRIA (2005)"},{"key":"4_CR9","first-page":"128","volume":"14","author":"G. Collins","year":"1967","unstructured":"Collins, G.: Subresultants and reduced polynomial remainder sequences. J.\u00a0ACM\u00a014, 128\u2013142 (1967)","journal-title":"J.\u00a0ACM"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1145\/800205.806346","volume-title":"SYMSAC 1976","author":"G. Collins","year":"1976","unstructured":"Collins, G., Akritas, A.: Polynomial real root isolation using Descartes\u2019 rule of signs. In: SYMSAC 1976, pp. 272\u2013275. ACM Press, New York (1976)"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-7091-3406-1_7","volume-title":"Computer Algebra: Symbolic and Algebraic Computation","author":"G. Collins","year":"1982","unstructured":"Collins, G., Loos, R.: Real zeros of polynomials. In: Buchberger, B., Collins, G., Loos, R. (eds.) Computer Algebra: Symbolic and Algebraic Computation, 2nd edn., pp. 83\u201394. Springer, Wien (1982)","edition":"2"},{"issue":"1\/2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0747-7171(88)80008-7","volume":"5","author":"M. Coste","year":"1988","unstructured":"Coste, M., Roy, M.F.: Thom\u2019s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets. J. Symb. Comput.\u00a05(1\/2), 121\u2013129 (1988)","journal-title":"J. Symb. Comput."},{"key":"4_CR13","unstructured":"Davenport, J.H.: Cylindrical algebraic decomposition. Technical Report 88\u201310, School of Mathematical Sciences, University of Bath, England (1988), http:\/\/www.bath.ac.uk\/masjhd\/"},{"key":"4_CR14","unstructured":"Du, Z., Sharma, V., Yap, C.K.: Amortized bound for root isolation via Sturm sequences. In: Wang, D., Zhi, L. (eds.) Int. Workshop on Symbolic Numeric Computing, School of Science, Beihang University, Beijing, China, pp. 81\u201393 (2005)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/11555964_12","volume-title":"Computer Algebra in Scientific Computing","author":"A. Eigenwillig","year":"2005","unstructured":"Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: A Descartes Algorithm for Polynomials with Bit-Stream Coefficients. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol.\u00a03718, pp. 138\u2013149. Springer, Heidelberg (2005)"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/1145768.1145786","volume-title":"ISSAC 2006: Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation","author":"A. Eigenwillig","year":"2006","unstructured":"Eigenwillig, A., Sharma, V., Yap, C.K.: Almost tight recursion tree bounds for the Descartes method. In: ISSAC 2006: Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, pp. 71\u201378. ACM Press, New York (2006)"},{"issue":"3","key":"4_CR17","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0747-7171(02)00135-9","volume":"35","author":"M. Kahoui El","year":"2003","unstructured":"El Kahoui, M.: An elementary approach to subresultants theory. J. Symb. Comput.\u00a035(3), 281\u2013292 (2003)","journal-title":"J. Symb. Comput."},{"key":"4_CR18","first-page":"438","volume-title":"Proc. Annual ACM Symp. on Computational Geometry","author":"I. Emiris","year":"2004","unstructured":"Emiris, I., Kakargias, A., Teillaud, M., Tsigaridas, E., Pion, S.: Towards an open curved kernel. In: Proc. Annual ACM Symp. on Computational Geometry, pp. 438\u2013446. ACM Press, New York (2004)"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1007\/978-3-540-30140-0_58","volume-title":"Algorithms \u2013 ESA 2004","author":"I. Emiris","year":"2004","unstructured":"Emiris, I., Tsigaridas, E.: Computing with real algebraic numbers of small degree. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 652\u2013663. Springer, Heidelberg (2004)"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/11555964_13","volume-title":"Proc. Computer Algebra in Scientific Computing (CASC)","author":"I. Emiris","year":"2005","unstructured":"Emiris, I., Tsigaridas, E.: Real solving of bivariate polynomial systems. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds.) Proc. Computer Algebra in Scientific Computing (CASC), pp. 150\u2013161. Springer, Heidelberg (2005)"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Emiris, I., Tsigaridas, E., Tzoumas, G.: The predicates for the Voronoi diagram of ellipses. In: Proc.\u00a022th Annual ACM Symp.\u00a0on Computational Geometry, Sedona, USA, pp. 227\u2013236 (2006)","DOI":"10.1145\/1137856.1137891"},{"key":"4_CR22","unstructured":"Emiris, I., Tsigaridas, E.P.: Computations with one and two algebraic numbers. Technical report, ArXiv (Dec 2005)"},{"key":"4_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/b102438","volume-title":"Algorithms of Computer Algebra","author":"K. Geddes","year":"1992","unstructured":"Geddes, K., Czapor, S., Labahn, G.: Algorithms of Computer Algebra. Kluwer Academic Publishers, Boston (1992)"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez-Vega, L., Lombardi, H., Recio, T., Roy, M.-F.: Sturm-Habicht Sequence. In: ISSAC, pp. 136\u2013146 (1989)","DOI":"10.1145\/74540.74558"},{"key":"4_CR25","unstructured":"Guibas, L., Karavelas, M., Russel, D.: A computational framework for handling motion. In: Proc. 6th Workshop Algor. Engin. & Experim. (ALENEX), January 2004, pp. 129\u2013141 (2004)"},{"issue":"4","key":"4_CR26","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321662.321667","volume":"18","author":"L.E. Heindel","year":"1971","unstructured":"Heindel, L.E.: Integer arithmetic algorithms for polynomial real zero determination. Journal of the Association for Computing Machinery\u00a018(4), 533\u2013548 (1971)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"4_CR27","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/978-3-7091-9459-1_13","volume-title":"Quantifier elimination and cylindrical algebraic decomposition","author":"J. Johnson","year":"1998","unstructured":"Johnson, J.: Algorithms for polynomial real root isolation. In: Caviness, B., Johnson, J. (eds.) Quantifier elimination and cylindrical algebraic decomposition, pp. 269\u2013299. Springer, Heidelberg (1998)"},{"key":"4_CR28","doi-asserted-by":"crossref","unstructured":"Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A CORE library for robust numeric and geometric computation. In: 15th ACM Symp. on Computational Geometry (1999)","DOI":"10.1145\/304893.304989"},{"key":"4_CR29","first-page":"105","volume-title":"Wissenschaftliches Rechnen","author":"W. Krandick","year":"1995","unstructured":"Krandick, W.: Isolierung reeller Nullstellen von Polynomen. In: Herzberger, J. (ed.) Wissenschaftliches Rechnen, pp. 105\u2013154. Akademie-Verlag, Berlin (1995)"},{"issue":"1","key":"4_CR30","first-page":"49","volume":"41","author":"W. Krandick","year":"2006","unstructured":"Krandick, W., Mehlhorn, K.: New bounds for the Descartes method. JSC\u00a041(1), 49\u201366 (2006)","journal-title":"JSC"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/BF01934076","volume":"21","author":"J.M. Lane","year":"1981","unstructured":"Lane, J.M., Riesenfeld, R.F.: Bounds on a polynomial. BIT\u00a021, 112\u2013117 (1981)","journal-title":"BIT"},{"issue":"3","key":"4_CR32","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1006\/jsco.2000.0427","volume":"31","author":"T. Lickteig","year":"2001","unstructured":"Lickteig, T., Roy, M.-F.: Sylvester-Habicht Sequences and Fast Cauchy Index Computation. J. Symb. Comput.\u00a031(3), 315\u2013341 (2001)","journal-title":"J. Symb. Comput."},{"issue":"4-5","key":"4_CR33","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1006\/jsco.1999.0322","volume":"29","author":"H. Lombardi","year":"2000","unstructured":"Lombardi, H., Roy, M.-F., Safey El Din, M.: New Structure Theorem for Subresultants. J. Symb. Comput.\u00a029(4-5), 663\u2013689 (2000)","journal-title":"J. Symb. Comput."},{"key":"4_CR34","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9171-5","volume-title":"Mathematics for Computer Algebra","author":"M. Mignotte","year":"1992","unstructured":"Mignotte, M.: Mathematics for Computer Algebra. Springer, Heidelberg (1992)"},{"issue":"6","key":"4_CR35","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01198012","volume":"6","author":"M. Mignotte","year":"1995","unstructured":"Mignotte, M.: On the Distance Between the Roots of a Polynomial. Appl. Algebra Eng. Commun. Comput.\u00a06(6), 327\u2013332 (1995)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"4_CR36","unstructured":"Mourrain, B., Pavone, J.P., Tr\u00e9buchet, P., Tsigaridas, E.: SYNAPS, a library for symbolic-numeric computation. In: 8th Int. Symposium on Effective Methods in Algebraic Geometry, MEGA, Sardinia, Italy, May 2005. Software presentation (2005)"},{"key":"4_CR37","series-title":"Mathematical Sciences Research Institute Publications","first-page":"459","volume-title":"Bernstein\u2019s basis and real root isolation","author":"B. Mourrain","year":"2005","unstructured":"Mourrain, B., Rouillier, F., Roy, M.-F.: Bernstein\u2019s basis and real root isolation. Mathematical Sciences Research Institute Publications, pp. 459\u2013478. Cambridge University Press, Cambridge (2005)"},{"issue":"2","key":"4_CR38","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.comgeo.2004.05.003","volume":"30","author":"B. Mourrain","year":"2005","unstructured":"Mourrain, B., T\u00e9court, J., Teillaud, M.: On the computation of an arrangement of quadrics in 3d. Comput. Geom.\u00a030(2), 145\u2013164 (2005)","journal-title":"Comput. Geom."},{"key":"4_CR39","doi-asserted-by":"crossref","unstructured":"Mourrain, B., Vrahatis, M., Yakoubsohn, J.: On the complexity of isolating real roots and computing with certainty the topological degree. J. Complexity\u00a018(2) (2002)","DOI":"10.1006\/jcom.2001.0636"},{"issue":"5","key":"4_CR40","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1006\/jsco.2002.0531","volume":"33","author":"V. Pan","year":"2002","unstructured":"Pan, V.: Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding. J.\u00a0Symbolic Computation\u00a033(5), 701\u2013733 (2002)","journal-title":"J.\u00a0Symbolic Computation"},{"key":"4_CR41","doi-asserted-by":"crossref","unstructured":"Reischert, D.: Asymptotically fast computation of subresultants. In: ISSAC, pp. 233\u2013240 (1997)","DOI":"10.1145\/258726.258792"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"Rioboo, R.: Towards faster real algebraic numbers. In: Proc. ACM Intern. Symp. on Symbolic & Algebraic Comput, Lille, France, pp. 221\u2013228 (2002)","DOI":"10.1145\/780506.780535"},{"issue":"1","key":"4_CR43","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.cam.2003.08.015","volume":"162","author":"F. Rouillier","year":"2004","unstructured":"Rouillier, F., Zimmermann, Z.: Efficient isolation of polynomial\u2019s real roots. J. of Computational and Applied Mathematics\u00a0162(1), 33\u201350 (2004)","journal-title":"J. of Computational and Applied Mathematics"},{"issue":"1","key":"4_CR44","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0747-7171(08)80035-1","volume":"10","author":"M.-F. Roy","year":"1990","unstructured":"Roy, M.-F., Szpirglas, A.: Complexity of the Computation on Real Algebraic Numbers. J. Symb. Comput.\u00a010(1), 39\u201352 (1990)","journal-title":"J. Symb. Comput."},{"key":"4_CR45","unstructured":"Sch\u00f6nhage, A.: The fundamental theorem of algebra in terms of computational complexity. Univ. of T\u00fcbingen, Germany (manuscript, 1982)"},{"key":"4_CR46","unstructured":"Sharma, V., Yap, C.: Sharp Amortized Bounds for Descartes and de Casteljau\u2019s Methods for Real Root Isolation (October 2005) (unpublished manuscript)"},{"key":"4_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1007\/11841036_72","volume-title":"Algorithms \u2013 ESA 2006","author":"E.P. Tsigaridas","year":"2006","unstructured":"Tsigaridas, E.P., Emiris, I.Z.: Univariate polynomial real root isolation: Continued fractions revisited. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 817\u2013828. Springer, Heidelberg (2006)"},{"key":"4_CR48","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J., Gerhard, J.: Fast Algorithms for Taylor Shifts and Certain Difference Equations. In: ISSAC, pp. 40\u201347 (1997)","DOI":"10.1145\/258726.258745"},{"key":"4_CR49","volume-title":"Modern Computer Algebra","author":"J. Gathen von zur","year":"2003","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge Univ. Press, Cambridge (2003)","edition":"2"},{"issue":"297","key":"4_CR50","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0304-3975(02)00639-4","volume":"1-3","author":"J. Gathen von zur","year":"2003","unstructured":"von zur Gathen, J., L\u00fccking, T.: Subresultants revisited. Theor. Comput. Sci.\u00a01-3(297), 199\u2013239 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR51","volume-title":"Fundamental Problems of Algorithmic Algebra","author":"C. Yap","year":"2000","unstructured":"Yap, C.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York (2000)"}],"container-title":["Lecture Notes in Computer Science","Reliable Implementation of Real Number Algorithms: Theory and Practice"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85521-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T09:39:46Z","timestamp":1738316386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85521-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540855200","9783540855217"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85521-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}