{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T11:35:31Z","timestamp":1786188931108,"version":"3.56.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,3,1]],"date-time":"2020-03-01T00:00:00Z","timestamp":1583020800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:p>Most numerical algorithms are designed for single or double precision floating point arithmetic, and their complexity is measured in terms of the total number of floating point operations. The resolution of problems with high condition numbers (e.g. when approaching a singularity or degeneracy) may require higher working precisions, in which case it is important to take the precision into account when doing complexity analyses. In this paper, we propose a new \"ultimate complexity\" model, which focuses on analyzing the cost of numerical algorithms for \"sufficiently large\" precisions. As an example application we will present an ultimately softly linear time algorithm for modular composition of univariate polynomials.<\/jats:p>","DOI":"10.1145\/3419048.3419049","type":"journal-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:53:25Z","timestamp":1597884805000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Ultimate complexity for numerical algorithms"],"prefix":"10.1145","volume":"54","author":[{"given":"Joris","family":"van der Hoeven","sequence":"first","affiliation":[{"name":"CNRS, \u00c9cole polytechnique, Institut Polytechnique de Paris, Palaiseau, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"additional","affiliation":[{"name":"CNRS, \u00c9cole polytechnique, Institut Polytechnique de Paris, Palaiseau, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Scaled remainder trees. Available from https:\/\/cr.yp.to\/arith\/scaledmod-20040820.pdf","author":"Bernstein D.","year":"2004","unstructured":"D. Bernstein . Scaled remainder trees. Available from https:\/\/cr.yp.to\/arith\/scaledmod-20040820.pdf , 2004 . D. Bernstein. Scaled remainder trees. Available from https:\/\/cr.yp.to\/arith\/scaledmod-20040820.pdf, 2004."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860870"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322099"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1963394"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38896-5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01178683"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2017.11.001"},{"key":"e_1_2_1_11_1","volume-title":"HAL, 2019","author":"Harvey D.","year":"2070","unstructured":"D. Harvey and J. van der Hoeven. Integer multiplication in time O(n log n). Technical report , HAL, 2019 . http:\/\/hal.archives-ouvertes.fr\/hal-0 2070 778. D. Harvey and J. van der Hoeven. Integer multiplication in time O(n log n). Technical report, HAL, 2019. http:\/\/hal.archives-ouvertes.fr\/hal-02070778."},{"key":"e_1_2_1_13_1","volume-title":"CNRS & \u00c9cole polytechnique","author":"van der Hoeven J.","year":"2011","unstructured":"J. van der Hoeven . Ball arithmetic. Technical report , CNRS & \u00c9cole polytechnique , 2011 . https:\/\/hal.archives-ouvertes.fr\/hal-00432152\/. J. van der Hoeven. Ball arithmetic. Technical report, CNRS & \u00c9cole polytechnique, 2011. https:\/\/hal.archives-ouvertes.fr\/hal-00432152\/."},{"key":"e_1_2_1_14_1","volume-title":"CNRS & \u00c9Ecole polytechnique","author":"van der Hoeven J.","year":"2016","unstructured":"J. van der Hoeven . Faster Chinese remaindering. Technical report , CNRS & \u00c9Ecole polytechnique , 2016 . http:\/\/hal.archives-ouvertes.fr\/hal-01403810. J. van der Hoeven. Faster Chinese remaindering. Technical report, CNRS & \u00c9Ecole polytechnique, 2016. http:\/\/hal.archives-ouvertes.fr\/hal-01403810."},{"key":"e_1_2_1_15_1","unstructured":"J. van der Hoeven etal GNU TeXmacs. http:\/\/www.texmacs.org 1998.  J. van der Hoeven et al. GNU TeXmacs. http:\/\/www.texmacs.org 1998."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2018.05.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2019.04.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258777"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00944-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.13"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02234767"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-76526-6"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0008"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2002.0531"},{"key":"e_1_2_1_28_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994","unstructured":"C. H. Papadimitriou . Computational Complexity . Addison-Wesley , 1994 . C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/11551.11552"},{"key":"e_1_2_1_32_1","volume-title":"Preliminary Report of Mathematisches Institut der Universit\u00e4t T\u00fcbingen","author":"Sch\u00f6nhage A.","year":"1982","unstructured":"A. Sch\u00f6nhage . The fundamental theorem of algebra in terms of computational complexity. Technical report , Preliminary Report of Mathematisches Institut der Universit\u00e4t T\u00fcbingen , Germany , 1982 . A. Sch\u00f6nhage. The fundamental theorem of algebra in terms of computational complexity. Technical report, Preliminary Report of Mathematisches Institut der Universit\u00e4t T\u00fcbingen, Germany, 1982."}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3419048.3419049","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3419048.3419049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:32:05Z","timestamp":1750195925000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3419048.3419049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["10.1145\/3419048.3419049"],"URL":"https:\/\/doi.org\/10.1145\/3419048.3419049","relation":{},"ISSN":["1932-2240"],"issn-type":[{"value":"1932-2240","type":"print"}],"subject":[],"published":{"date-parts":[[2020,3]]},"assertion":[{"value":"2020-08-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}