{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:10:24Z","timestamp":1738350624728,"version":"3.35.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T00:00:00Z","timestamp":1738022400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T00:00:00Z","timestamp":1738022400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer. Math."],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s00211-025-01454-x","type":"journal-article","created":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T03:19:37Z","timestamp":1738034377000},"page":"355-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast evaluation of real and complex polynomials"],"prefix":"10.1007","volume":"157","author":[{"given":"Ramona","family":"Anton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolae","family":"Mihalache","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Vigneron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,28]]},"reference":[{"issue":"2","key":"1454_CR1","doi-asserted-by":"publisher","first-page":"1280","DOI":"10.1137\/120864581","volume":"51","author":"R Barrio","year":"2013","unstructured":"Barrio, R., Jiang, H., Serrano, S.: A general condition number for polynomials. SIAM J. Numer. Anal. 51(2), 1280\u20131294 (2013)","journal-title":"SIAM J. Numer. Anal."},{"key":"1454_CR2","volume-title":"Approximations spectrales de probl\u00e8me aux limite elliptiques","author":"C Bernardi","year":"1992","unstructured":"Bernardi, C., Maday, Y.: Approximations spectrales de probl\u00e8me aux limite elliptiques. Springer, Cham (1992)"},{"issue":"4","key":"1454_CR3","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.jco.2004.09.009","volume":"21","author":"A Bostan","year":"2005","unstructured":"Bostan, A., Schost, E.: Polynomial evaluation and interpolation on special sets of points. J. Complex. 21(4), 420\u2013446 (2005)","journal-title":"J. Complex."},{"key":"1454_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4364-9","volume-title":"Complex dynamics","author":"L Carleson","year":"1993","unstructured":"Carleson, L., Gamelin, T.W.: Complex dynamics. Springer, Cham (1993)"},{"key":"1454_CR5","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1090\/S0025-5718-1955-0071856-0","volume":"9","author":"CW Clenshaw","year":"1955","unstructured":"Clenshaw, C.W.: A note on the summation of Chebyshev series. Math. Tables Aids Comput. 9, 118\u2013120 (1955)","journal-title":"Math. Tables Aids Comput."},{"issue":"90","key":"1454_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"1454_CR7","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1007\/s11075-020-00996-5","volume":"87","author":"F Chudy","year":"2021","unstructured":"Chudy, F., Wo\u017any, P.: Fast and accurate evaluation of dual Bernstein polynomials. Numer. Algor. 87, 1001\u20131015 (2021)","journal-title":"Numer. Algor."},{"key":"1454_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0016-0032(42)90767-1","volume":"233","author":"GC Danielson","year":"1942","unstructured":"Danielson, G.C., Lanczos, C.: Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids. J. Franklin Inst. 233, 365\u2013380 (1942)","journal-title":"J. Franklin Inst."},{"key":"1454_CR9","doi-asserted-by":"crossref","unstructured":"Estrin, G.: Organization of computer systems: the fixed plus variable structure computer. In: ACM, editor, Papers presented at the May 3-5, 1960, western joint IRE-AIEE-ACM computer conference, pp. 33\u201340, (1960)","DOI":"10.1145\/1460361.1460365"},{"key":"1454_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01386049","volume":"6","author":"J Eve","year":"1964","unstructured":"Eve, J.: The evaluation of polynomials. Numer. Math. 6, 17\u201321 (1964)","journal-title":"Numer. Math."},{"key":"1454_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73398-0","volume-title":"Pythagorean hodograph curves: algebra and geometry inseparable","author":"RT Farouki","year":"2008","unstructured":"Farouki, R.T.: Pythagorean hodograph curves: algebra and geometry inseparable. Springer, Cham (2008)"},{"issue":"6","key":"1454_CR12","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.cagd.2012.03.001","volume":"29","author":"RT Farouki","year":"2012","unstructured":"Farouki, R.T.: The Bernstein polynomial basis: a centennial retrospective. Comput. Aided Geometric Design 29(6), 379\u2013419 (2012)","journal-title":"Comput. Aided Geometric Design"},{"issue":"1","key":"1454_CR13","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.laa.2019.04.001","volume":"574","author":"M Fasi","year":"2019","unstructured":"Fasi, M.: Optimality of the Paterson-Stockmeyer method for evaluating matrix polynomials and rational matrix functions. Linear Algebra Appl. 574(1), 182\u2013200 (2019)","journal-title":"Linear Algebra Appl."},{"key":"1454_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/103162.103163","volume":"23","author":"D Goldberg","year":"1991","unstructured":"Goldberg, D.: What every computer scientist should know about floating-point arithmetic. ACM Comput. Surv. 23, 5\u201348 (1991)","journal-title":"ACM Comput. Surv."},{"key":"1454_CR15","doi-asserted-by":"crossref","unstructured":"Hammersley, J.M.: The zeros of a random polynomial. In Berkeley University of California Press, editor, Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability 2, 89\u2013111 (1956)","DOI":"10.1525\/9780520350670-010"},{"key":"1454_CR16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027","volume-title":"Accuracy and stability of numerical algorithms","author":"NJ Higham","year":"2002","unstructured":"Higham, N.J.: Accuracy and stability of numerical algorithms. SIAM, Philadelphia (2002)"},{"key":"1454_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s002220100149","volume":"146","author":"JH Hubbard","year":"2001","unstructured":"Hubbard, J.H., Schleicher, D., Sutherland, S.: How to find all roots of complex polynomials by Newton\u2019s method. Invent. Math. 146, 1\u201333 (2001)","journal-title":"Invent. Math."},{"key":"1454_CR18","unstructured":"IEEE\u00a0754. https:\/\/en.wikipedia.org\/wiki\/IEEE_754"},{"key":"1454_CR19","doi-asserted-by":"crossref","unstructured":"Kalman, D.: Uncommon Mathematical Excursions, volume\u00a035 of Dolciani Mathematical Expositions. Mathematical Association of America, (2008)","DOI":"10.1090\/dol\/035"},{"issue":"12","key":"1454_CR20","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/355580.369074","volume":"5","author":"DE Knuth","year":"1962","unstructured":"Knuth, D.E.: Evaluation of polynomials by computer. Commun. ACM 5(12), 595\u2013599 (1962)","journal-title":"Commun. ACM"},{"key":"1454_CR21","unstructured":"Kobel, A., Sagraloff, M.: Fast approximate polynomial multipoint evaluation and applications. arXiv:1304.8069, (2016)"},{"key":"1454_CR22","unstructured":"K\u00f6hler, S., Ziegler, M.: On the stability of fast polynomial arithmetic. Proceedings of the 8th Conference on Real Numbers and Computers, pp. 147\u2013156, (2008)"},{"key":"1454_CR23","unstructured":"Langlois, P., Graillat, S., Louvet, N.: Compensated H\u00f6rner scheme. In Algebraic and Numerical Algorithms and Computer-assisted Proofs, volume 5391 of Dagstuhl Seminar Proceedings (DagSemProc), (2006)"},{"key":"1454_CR24","doi-asserted-by":"crossref","unstructured":"Muller, J.-M., al.: Handbook of Floating-Point Arithmetic. Birkh\u00e4user, (2018)","DOI":"10.1007\/978-3-319-76526-6"},{"key":"1454_CR25","volume-title":"Dynamics in one complex variable. Number 160 in Annals of Mathematics Studies","author":"J Milnor","year":"1990","unstructured":"Milnor, J.: Dynamics in one complex variable. Number 160 in Annals of Mathematics Studies. Princeton University Press, Princeton (1990)"},{"key":"1454_CR26","unstructured":"Moroz, G.: Fast polynomial evaluation and composition. Technical Report 453, Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, (2013)"},{"issue":"1","key":"1454_CR27","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0202007","volume":"2","author":"LJ Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.J., Paterson, M.S.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60\u201366 (1973)","journal-title":"SIAM J. Comput."},{"key":"1454_CR28","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02242136","volume":"30","author":"KH M\u00fcller","year":"1983","unstructured":"M\u00fcller, K.H.: Rounding error analysis of H\u00f6rner\u2019s scheme. Computing 30, 285\u2013303 (1983)","journal-title":"Computing"},{"key":"1454_CR29","unstructured":"Mihalache, N., Vigneron, F.: How to split a tera-polynomial. In preparation"},{"issue":"2","key":"1454_CR30","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0771-050X(79)90002-0","volume":"5","author":"J Oliver","year":"1979","unstructured":"Oliver, J.: Rounding error propagation in polynomial evaluation schemes. J. Comput. Appl. Math. 5(2), 85\u201397 (1979)","journal-title":"J. Comput. Appl. Math."},{"key":"1454_CR31","doi-asserted-by":"crossref","unstructured":"Ostrowski, A.M.: On two problems in abstract algebra connected with H\u00f6rner\u2019s rule. Studies in Mathematics and Mechanics, pp. 40\u201348, (1954)","DOI":"10.1016\/B978-1-4832-3272-0.50010-7"},{"key":"1454_CR32","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1070\/RM1966v021n01ABEH004147","volume":"21","author":"V\u00a0Ja Pan","year":"1966","unstructured":"Pan, V\u00a0Ja.: On means of calculating values of polynomials. Russian Math. Surv. 21, 105\u2013136 (1966)","journal-title":"Russian Math. Surv."},{"issue":"1","key":"1454_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02431995","volume":"3","author":"VY Pan","year":"1995","unstructured":"Pan, V.Y.: An algebraic approach to approximate evaluation of a polynomial on a set of real points. Adv. Comput. Math. 3(1), 41\u201358 (1995)","journal-title":"Adv. Comput. Math."},{"issue":"4","key":"1454_CR34","doi-asserted-by":"publisher","first-page":"1186","DOI":"10.1137\/S0036142997324150","volume":"37","author":"JM Pena","year":"2000","unstructured":"Pena, J.M., Sauer, T.: On the multivariate H\u00f6rner scheme. SIAM J. Numer. Anal. 37(4), 1186\u20131197 (2000)","journal-title":"SIAM J. Numer. Anal."},{"key":"1454_CR35","doi-asserted-by":"crossref","unstructured":"Potts, D., Steidl, G., Tasche, M.: Fast Fourier transforms for nonequispaced data: A tutorial, in Modern Sampling Theory: Mathematics and Applications. Birkh\u00e4user, (2001)","DOI":"10.1007\/978-1-4612-0143-4_12"},{"key":"1454_CR36","first-page":"1","volume":"1","author":"D Potts","year":"2002","unstructured":"Potts, D., Steidl, G., Tasche, M.: Numerical stability of fast trigonometric transforms: a worst case study. Concrete Appl. Math. 1, 1\u201336 (2002)","journal-title":"Concrete Appl. Math."},{"issue":"6","key":"1454_CR37","first-page":"2059","volume":"28","author":"JH Reif","year":"1999","unstructured":"Reif, J.H.: Approximate complex polynomial evaluation in near constant work per point. J. Comput. 28(6), 2059\u20132089 (1999)","journal-title":"J. Comput."},{"issue":"1","key":"1454_CR38","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1112\/jlms\/s1-7.1.10","volume":"7","author":"F Riesz","year":"1932","unstructured":"Riesz, F.: Sur un th\u00e9or\u00e8me de maximum de MM. Hardy et Littlewood. J. Lond. Math. Soc. 7(1), 10\u201313 (1932)","journal-title":"J. Lond. Math. Soc."},{"issue":"1","key":"1454_CR39","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1109\/5992.814659","volume":"2","author":"DN Rockmore","year":"2000","unstructured":"Rockmore, D.N.: The FFT: an algorithm the whole family can use. Comput. Sci. Eng. 2(1), 60\u201364 (2000)","journal-title":"Comput. Sci. Eng."},{"key":"1454_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/3-540-11607-9_1","volume-title":"Computer Algebra","author":"A Sch\u00f6nhage","year":"1982","unstructured":"Sch\u00f6nhage, A.: Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients. In: Calmet, J. (ed.) Computer Algebra. Lecture Notes in Computer Science, vol. 144, pp. 3\u201315. Springer, Cham (1982)"},{"key":"1454_CR41","volume-title":"Higher-order finite element methods","author":"P Solin","year":"2004","unstructured":"Solin, P., Segeth, K., Dolezel, I.: Higher-order finite element methods. Chapman & Hall\/CRC, London (2004)"},{"key":"1454_CR42","unstructured":"Sutin, B.M.: Accurate evaluation of polynomials. arXiv:0805.3194, (2007)"},{"key":"1454_CR43","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s11075-004-4570-4","volume":"38","author":"A Smoktunowicz","year":"2005","unstructured":"Smoktunowicz, A., Wr\u00f3bel, I.: On improving the accuracy of H\u00f6rner\u2019s and Goertzel\u2019s algorithms. Numerical Algorithms 38, 243\u2013258 (2005)","journal-title":"Numerical Algorithms"},{"key":"1454_CR44","doi-asserted-by":"crossref","unstructured":"Shiffman, B., Zelditch, S.: Equilibrium distribution of zeros of random polynomials. International Mathematical Research Notices, pp. 25\u201349, (2003)","DOI":"10.1155\/S1073792803206073"},{"key":"1454_CR45","unstructured":"Wilkinson, J.H.: The perfidious polynomial, pages 1\u201328. Studies in Numerical Analysis. G. H. Golub, (1984)"},{"key":"1454_CR46","unstructured":"Hart, W., Johansson, F., Pancratz, S.: FLINT: Fast Library for Number Theory. http:\/\/flintlib.org, (2013)"},{"key":"1454_CR47","unstructured":"Mihalache, N., Vigneron, F.: FPE library: a Fast Polynomial Evaluator. https:\/\/github.com\/fvigneron\/FastPolyEval, (2022)"},{"issue":"2","key":"1454_CR48","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1236463.1236468","volume":"33","author":"L Fousse","year":"2007","unstructured":"Fousse, L., Hanrot, G., Lef\u00e8vre, V., P\u00e9lissier, P., Zimmermann, P.: MPFR: a Multiple-Precision binary Floating-point library with correct Rounding. ACM Trans. Math. Software 33(2), 13\u201328 (2007)","journal-title":"ACM Trans. Math. Software"}],"container-title":["Numerische Mathematik"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-025-01454-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00211-025-01454-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-025-01454-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:54:25Z","timestamp":1738349665000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00211-025-01454-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,28]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["1454"],"URL":"https:\/\/doi.org\/10.1007\/s00211-025-01454-x","relation":{},"ISSN":["0029-599X","0945-3245"],"issn-type":[{"type":"print","value":"0029-599X"},{"type":"electronic","value":"0945-3245"}],"subject":[],"published":{"date-parts":[[2025,1,28]]},"assertion":[{"value":"25 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}