{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T03:11:53Z","timestamp":1783653113028,"version":"3.55.0"},"reference-count":107,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T00:00:00Z","timestamp":1772323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T00:00:00Z","timestamp":1772323200000},"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":["AAECC"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s00200-025-00719-0","type":"journal-article","created":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T09:34:23Z","timestamp":1773135263000},"page":"331-387","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Towards a library for straight-line programs"],"prefix":"10.1007","volume":"37","author":[{"given":"Joris","family":"van der Hoeven","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,10]]},"reference":[{"key":"719_CR1","unstructured":"Ahlb\u00e4ck, A., van der Hoeven, J., Lecerf, G.: JIL: a high performance library for straight-line programs. (2025). https:\/\/sourcesup.renater.fr\/projects\/jil"},{"key":"719_CR2","doi-asserted-by":"crossref","unstructured":"Ahlb\u00e4ck, A., Johansson, F.: Fast basecases for arbitrary-size multiplication. In 2025 IEEE 32nd Symposium on Computer Arithmetic (ARITH), pp. 53\u201360. (2025)","DOI":"10.1109\/ARITH64983.2025.00018"},{"key":"719_CR3","volume-title":"Compilers principles, techniques & tools","author":"AV Aho","year":"2007","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers principles, techniques & tools, 2nd edn. Pearson Education, Pearson Education (2007)","edition":"2"},{"key":"719_CR4","volume-title":"Numerical Continuation Methods","author":"K Georg","year":"1990","unstructured":"Georg, K., Allgower, E.L.: Numerical Continuation Methods. Springer-Verlag, Berlin (1990)"},{"key":"719_CR5","unstructured":"ANSI\/IEEE. IEEE standard for binary floating-point arithmetic. Technical Report, ANSI\/IEEE, New York, 2008. ANSI-IEEE Standard 754-2008. Revision of IEEE 754-1985, approved on June 12, 2008 by IEEE Standards Board"},{"key":"719_CR6","unstructured":"ARM corporation. Fast models user guide. https:\/\/developer.arm.com\/documentation\/100965\/latest. Version 11.29"},{"key":"719_CR7","doi-asserted-by":"crossref","unstructured":"Aschenbrenner, M., van\u00a0den Dries, L., van\u00a0der Hoeven, J.: Asymptotic Differential Algebra and Model Theory of Transseries. Number 195 in Annals of Mathematics studies. Princeton University Press (2017)","DOI":"10.23943\/princeton\/9780691175423.001.0001"},{"key":"719_CR8","unstructured":"AsmJit: low-latency machine code generation. https:\/\/github.com\/asmjit\/asmjit"},{"key":"719_CR9","unstructured":"Autodiff: automatic differentiation in C++ couldn\u2019t be simpler. https:\/\/autodiff.github.io"},{"key":"719_CR10","unstructured":"Torch.autograd: automatic differentiation package in pytorch. https:\/\/docs.pytorch.org\/docs\/stable\/autograd.html"},{"key":"719_CR11","unstructured":"Awesome-JIT. https:\/\/github.com\/wdv4758h\/awesome-jit. Ressources for JIT compilation"},{"key":"719_CR12","unstructured":"Bailey, D.\u00a0H., Hida, Y., Li, X.\u00a0S.: Algorithms for quad-double precision floating point arithmetic. In 15th IEEE Symposium on Computer Arithmetic, pp. 155\u2013162. IEEE (2001)"},{"issue":"1","key":"719_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/130722.130735","volume":"27","author":"HG Baker","year":"1992","unstructured":"Baker, H.G.: Computing A*B (mod N) efficiently in ANSI C. SIGPLAN Not. 27(1), 95\u201398 (1992)","journal-title":"SIGPLAN Not."},{"key":"719_CR14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W Baur","year":"1983","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comput. Sci. 22, 317\u2013330 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"719_CR15","unstructured":"Blas (basic linear algebra subprograms). https:\/\/netlib.org\/blas\/"},{"key":"719_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02920362","volume":"6","author":"JL Bordewijk","year":"1956","unstructured":"Bordewijk, J.L.: Inter-reciprocity applied to electrical networks. Appl. Sci. Res. B: Electrophysics, Acoustics, Optics, Mathematical Methods 6, 1\u201374 (1956)","journal-title":"Appl. Sci. Res. B: Electrophysics, Acoustics, Optics, Mathematical Methods"},{"key":"719_CR17","doi-asserted-by":"crossref","unstructured":"Bostan, A., Lecerf, G., Schost, \u00c9.: Tellegen\u2019s principle into practice. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201903, pages 37\u201344. New York, NY, USA. ACM Press (2003)","DOI":"10.1145\/860854.860870"},{"key":"719_CR18","unstructured":"Bradbury, J., Drucker, N., Hillenbrand, M.: NTT software optimization using an extended Harvey butterfly. Cryptology ePrint Archive, Paper 2021\/1396 (2021). https:\/\/eprint.iacr.org\/2021\/1396"},{"key":"719_CR19","doi-asserted-by":"crossref","unstructured":"Briggs, P., Cooper, K.\u00a0D., Torczon, L.: Rematerialization. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation, PLDI \u201992, pages 311\u2013321. New York, NY, USA. ACM (1992)","DOI":"10.1145\/143095.143143"},{"issue":"6","key":"719_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/S0378-4754(02)00035-6","volume":"60","author":"N Bruno","year":"2002","unstructured":"Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R.: Functional programming concepts and straight-line programs in computer algebra. Math. Comput. Simul. 60(6), 423\u2013473 (2002)","journal-title":"Math. Comput. Simul."},{"key":"719_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","author":"P B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory. Springer-Verlag, Berlin (1997)"},{"issue":"5","key":"719_CR22","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/S0378-4754(99)00140-8","volume":"51","author":"B Casta\u00f1o","year":"2000","unstructured":"Casta\u00f1o, B., Heintz, J., Llovet, J., Mart\u00ecnez, R.: On the data structure straight-line program and its implementation in symbolic computation. Math. Comput. Simulation 51(5), 497\u2013528 (2000)","journal-title":"Math. Comput. Simulation"},{"issue":"6","key":"719_CR23","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/872726.806984","volume":"17","author":"GJ Chaitin","year":"1982","unstructured":"Chaitin, G.J.: Register allocation & spilling via graph coloring. ACM Sigplan Notices 17(6), 98\u2013101 (1982)","journal-title":"ACM Sigplan Notices"},{"issue":"1","key":"719_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"GJ Chaitin","year":"1981","unstructured":"Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. J. Comput. Lang. 6(1), 47\u201357 (1981)","journal-title":"J. Comput. Lang."},{"issue":"3","key":"719_CR25","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/BF01397083","volume":"18","author":"TJ Dekker","year":"1971","unstructured":"Dekker, T.J.: A floating-point technique for extending the available precision. Numer. Math. 18(3), 224\u2013242 (1971)","journal-title":"Numer. Math."},{"key":"719_CR26","doi-asserted-by":"crossref","unstructured":"D\u00edaz, A., Kaltofen, E.: FoxBox : a system for manipulating symbolic objects in black box representation. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201998, pages 30\u201337. New York, NY, USA (1998)","DOI":"10.1145\/281508.281538"},{"key":"719_CR27","doi-asserted-by":"crossref","unstructured":"Dumas, J.-G., Gautier, T., Giesbrecht, M., Giorgi, P., Hovinen, B., Kaltofen, E., Saunders, B.\u00a0D., Turner, W.\u00a0J., Villard, G.: LinBox: a generic library for exact linear algebra. In A.\u00a0M.\u00a0Cohen, X.\u00a0S.\u00a0Gao, and N.\u00a0Takayama, editors, Proceedings of the 2002 International Congress of Mathematical Software, Beijing, China, pp. 40\u201350. World Scientific, (2002). https:\/\/linalg.org","DOI":"10.1142\/9789812777171_0005"},{"key":"719_CR28","doi-asserted-by":"crossref","unstructured":"Dumas, J.-G., Giorgi, P., Pernet, C.: FFPACK: finite field linear algebra package. In J.\u00a0Schicho, editor, Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201904, pp. 119\u2013126. New York, NY, USA (2004)","DOI":"10.1145\/1005285.1005304"},{"issue":"3","key":"719_CR29","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1391989.1391992","volume":"35","author":"J-G Dumas","year":"2008","unstructured":"Dumas, J.-G., Giorgi, P., Pernet, C.: Dense linear algebra over word-size prime fields: the FFLAS and FFPACK packages. ACM Trans. Math. Softw. 35(3), 19\u20131 (2008)","journal-title":"ACM Trans. Math. Softw."},{"issue":"2","key":"719_CR30","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.exmath.2007.07.001","volume":"26","author":"C Durvye","year":"2008","unstructured":"Durvye, C., Lecerf, G.: A concise proof of the Kronecker polynomial system solver from scratch. Expo. Math. 26(2), 101\u2013139 (2008)","journal-title":"Expo. Math."},{"key":"719_CR31","doi-asserted-by":"crossref","unstructured":"Edamatsu, T., Takahashi, D.: Accelerating large integer multiplication using Intel AVX-512IFMA. In Algorithms and Architectures for Parallel Processing: 19th International Conference, ICA3PP 2019, Melbourne, Australia, pages 60\u201374. Springer-Verlag (2019)","DOI":"10.1007\/978-3-030-38991-8_5"},{"key":"719_CR32","unstructured":"Fiduccia, C.\u00a0M.: On the algebraic complexity of matrix multiplication. PhD thesis, Brown University (1973)"},{"key":"719_CR33","unstructured":"Fitchas, N., Giusti, M., Smietanski, F.: Sur la complexit\u00e9 du th\u00e9or\u00e8me des z\u00e9ros. In M.\u00a0Florenzano and J.\u00a0Guddat, editors, Approximation and optimization in the Caribbean, II (Havana, 1993), volume\u00a08 of Approx. Optim., pages 274\u2013329. Frankfurt am Main. Lang (1995)"},{"key":"719_CR34","unstructured":"Fog, A.: Software optimization resources. https:\/\/www.agner.org\/optimize"},{"key":"719_CR35","doi-asserted-by":"crossref","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), 2007. Software available at https:\/\/www.mpfr.org","DOI":"10.1145\/1236463.1236468"},{"key":"719_CR36","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/44128.214376","volume":"14","author":"TS Freeman","year":"1988","unstructured":"Freeman, T.S., Imirzian, G.M., Kaltofen, E., Lakshman, Y.: DAGWOOD: a system for manipulating polynomials given by straight-line programs. ACM Trans. Math. Software 14, 218\u2013240 (1988)","journal-title":"ACM Trans. Math. Software"},{"key":"719_CR37","doi-asserted-by":"crossref","unstructured":"Frigo, M.: A fast Fourier transform compiler. In Proc. 1999 ACM SIGPLAN Conf. on Programming Language Design and Implementation 34, 169\u2013180 (1999)","DOI":"10.1145\/301618.301661"},{"issue":"2","key":"719_CR38","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","volume":"93","author":"M Frigo","year":"2005","unstructured":"Frigo, M., Johnson, S.G.: The design and implementation of FFTW3. Proc. IEEE 93(2), 216\u2013231 (2005)","journal-title":"Proc. IEEE"},{"key":"719_CR39","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.\u00a0E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science, pp. 285\u2013297. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"719_CR40","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern Computer Algebra","author":"J Von Zur Gathen","year":"2013","unstructured":"Von Zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, Cambridge (2013)","edition":"3"},{"issue":"118","key":"719_CR41","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0022-4049(97)00015-7","volume":"117","author":"M Giusti","year":"1997","unstructured":"Giusti, M., H\u00e4gele, K., Heintz, J., Monta\u00f1a, J.L., Morais, J.E., Pardo, L.M.: Lower bounds for diophantine approximations. J. Pure Appl. Algebra 117(118), 277\u2013317 (1997)","journal-title":"J. Pure Appl. Algebra"},{"issue":"3","key":"719_CR42","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1006\/jsco.2000.0369","volume":"30","author":"M Giusti","year":"2000","unstructured":"Giusti, M., H\u00e4gele, K., Lecerf, G., Marchand, J., Salvy, B.: The projective Noether Maple package: computing the dimension of a projective variety. J. Symbolic Comput. 30(3), 291\u2013307 (2000)","journal-title":"J. Symbolic Comput."},{"key":"719_CR43","unstructured":"Giusti, M., Heintz, J.: La d\u00e9termination des points isol\u00e9s et de la dimension d\u2019une vari\u00e9t\u00e9 alg\u00e9brique peut se faire en temps polynomial. In D.\u00a0Eisenbud and L.\u00a0Robbiano, editors, Computational algebraic geometry and commutative algebra (Cortona, 1991), Sympos. Math., XXXIV, pp. 216\u2013256. Cambridge Univ. Press (1993)"},{"issue":"1\u20133","key":"719_CR44","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0022-4049(96)00099-0","volume":"124","author":"M Giusti","year":"1998","unstructured":"Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M.: Straight-line programs in geometric elimination theory. J. Pure Appl. Algebra 124(1\u20133), 101\u2013146 (1998)","journal-title":"J. Pure Appl. Algebra"},{"key":"719_CR45","doi-asserted-by":"crossref","unstructured":"Giusti, M., Heintz, J., Morais, J.\u00a0E., Pardo, L.\u00a0M.: When polynomial equation systems can be \u201csolved\u201d fast? In G.\u00a0Cohen, M.\u00a0Giusti, and T.\u00a0Mora, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1995, volume 948 of Lect. Notes Comput. Sci., pages 205\u2013231. Springer-Verlag (1995)","DOI":"10.1007\/3-540-60114-7_16"},{"issue":"11","key":"719_CR46","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1016\/S0764-4442(97)83558-6","volume":"325","author":"M Giusti","year":"1997","unstructured":"Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M.: Le r\u00f4le des structures de donn\u00e9es dans les probl\u00e8mes d\u2019\u00e9limination. C. R. Acad. Sci. Paris S\u00e9r. I Math. 325(11), 1223\u20131228 (1997)","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. I Math."},{"issue":"1","key":"719_CR47","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/BF01200407","volume":"3","author":"M Giusti","year":"1993","unstructured":"Giusti, M., Heintz, J., Sabia, J.: On the efficiency of effective Nullstellens\u00e4tze. Comput. Complexity 3(1), 56\u201395 (1993)","journal-title":"Comput. Complexity"},{"issue":"1","key":"719_CR48","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M Giusti","year":"2001","unstructured":"Giusti, M., Lecerf, G., Salvy, B.: A Gr\u00f6bner free alternative for polynomial system solving. J. Complexity 17(1), 154\u2013211 (2001)","journal-title":"J. Complexity"},{"key":"719_CR49","unstructured":"Granlund, T., et\u00a0al.: GMP, the GNU multiple precision arithmetic library. (1991). https:\/\/gmplib.org"},{"key":"719_CR50","doi-asserted-by":"crossref","unstructured":"Gueron, S., Krasnov, V.: Accelerating big integer arithmetic using intel IFMA extensions. In 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH), pp. 32\u201338 (2016)","DOI":"10.1109\/ARITH.2016.22"},{"issue":"2","key":"719_CR51","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0022-4049(98)00148-0","volume":"146","author":"K H\u00e4gele","year":"2000","unstructured":"H\u00e4gele, K., Morais, J.E., Pardo, L.M., Sombra, M.: On the intrinsic complexity of the arithmetic Nullstellensatz. J. Pure Appl. Algebra 146(2), 103\u2013183 (2000)","journal-title":"J. Pure Appl. Algebra"},{"key":"719_CR52","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s00200-003-0144-2","volume":"14","author":"G Hanrot","year":"2004","unstructured":"Hanrot, G., Quercia, M., Zimmermann, P.: The middle product algorithm I. Speeding up the division and square root of power series. Appl. Algebra Eng. Commun. Comput. 14, 415\u2013438 (2004)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"719_CR53","unstructured":"Hart, W., Johansson, F., Pancratz, S.: FLINT: Fast Library for Number Theory (2013). Version 2.4.0, https:\/\/flintlib.org"},{"key":"719_CR54","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.jsc.2013.09.002","volume":"60","author":"D Harvey","year":"2014","unstructured":"Harvey, D.: Faster arithmetic for number-theoretic transforms. J. Symbolic Comput. 60, 113\u2013119 (2014)","journal-title":"J. Symbolic Comput."},{"key":"719_CR55","unstructured":"Heintz, J., Schnorr, C.-P.: Testing polynomials which are easy to compute. In Logic and algorithmic (Zurich, 1980), volume\u00a030 of Monograph. Enseign. Math., pp. 237\u2013254. Geneva (1982). Univ. Gen\u00e8ve"},{"key":"719_CR56","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J.: The truncated Fourier transform and applications. In J.\u00a0Schicho, editor, Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201904, pages 290\u2013296. New York, NY, USA (2004)","DOI":"10.1145\/1005285.1005327"},{"key":"719_CR57","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1006\/jsco.2002.0562","volume":"34","author":"J van der Hoeven","year":"2002","unstructured":"van der Hoeven, J.: Relax, but don\u2019t be too lazy. J. Symbolic Comput. 34, 479\u2013542 (2002)","journal-title":"J. Symbolic Comput."},{"key":"719_CR58","unstructured":"Van\u00a0der Hoeven, J.: Notes on the Truncated Fourier Transform. Technical Report 2005-5, Universit\u00e9 Paris-Sud, Orsay, France (2005)"},{"key":"719_CR59","unstructured":"Van\u00a0der Hoeven, J.: Ball arithmetic. Technical Report, HAL, 2009. https:\/\/hal.archives-ouvertes.fr\/hal-00432152"},{"key":"719_CR60","unstructured":"Van\u00a0der Hoeven, J.: Ball arithmetic. In A.\u00a0Beckmann, Ch.\u00a0Ga\u00dfner, and B.\u00a0L\u00f6we, editors, Logical approaches to Barriers in Computing and Complexity, number\u00a06 in Preprint-Reihe Mathematik, pages 179\u2013208. Ernst-Moritz-Arndt-Universit\u00e4t Greifswald (2010)"},{"key":"719_CR61","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J.: Calcul analytique. In Journ\u00e9es Nationales de Calcul Formel. 14 \u2013 18 Novembre 2011, volume\u00a01 of Les cours du CIRM, pages 1\u201385. CIRM (2011). https:\/\/www.numdam.org\/articles\/10.5802\/ccirm.16\/","DOI":"10.5802\/ccirm.16"},{"key":"719_CR62","unstructured":"Van\u00a0der Hoeven, J.: Reliable homotopy continuation. Technical Report, HAL (2011). http:\/\/hal.archives-ouvertes.fr\/hal-00589948"},{"key":"719_CR63","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J.: Faster relaxed multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC \u201914, pages 405\u2013412. New York, NY, USA (2014)","DOI":"10.1145\/2608628.2608657"},{"key":"719_CR64","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J.: Multiple precision floating-point arithmetic on SIMD processors. In 24th IEEE Symposium on Computer Arithmetic (ARITH), pages 2\u20139 (2017)","DOI":"10.1109\/ARITH.2017.12"},{"key":"719_CR65","volume-title":"The Jolly Writer","author":"J van der Hoeven","year":"2020","unstructured":"van der Hoeven, J.: The Jolly Writer. Scypress, Your Guide to GNU TeXmacs (2020)"},{"key":"719_CR66","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J., Larrieu, R., Lecerf, G.: Implementing fast carryless multiplication. In Mathematical Aspects of Computer and Information Sciences. MACIS 2017, volume 10693 of Lect. Notes in Comput. Sci., pages 121\u2013136. Springer International Publishing (2017)","DOI":"10.1007\/978-3-319-72453-9_9"},{"key":"719_CR67","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J., Lecerf, G.: Interfacing Mathemagix with C++. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC \u201913, pages 363\u2013370. New York, NY, USA (2013)","DOI":"10.1145\/2465506.2465511"},{"key":"719_CR68","unstructured":"Van\u00a0der Hoeven, J., Lecerf, G.: Mathemagix User Guide. HAL (2013). https:\/\/hal.archives-ouvertes.fr\/hal-00785549"},{"key":"719_CR69","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J., Lecerf, G.: Faster FFTs in medium precision. In 22nd IEEE Symposium on Computer Arithmetic (ARITH), pages 75\u201382 (2015)","DOI":"10.1109\/ARITH.2015.10"},{"key":"719_CR70","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Hoeven, J., Lecerf, G.: Evaluating straight-line programs over balls. In P.\u00a0Montuschi, M.\u00a0Schulte, J.\u00a0Hormigo, S.\u00a0Oberman, and N.\u00a0Revol, editors, 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH), pages 142\u2013149. IEEE (2016). Preprint version at https:\/\/hal.science\/hal-01225979","DOI":"10.1109\/ARITH.2016.12"},{"key":"719_CR71","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10208-020-09453-0","volume":"21","author":"J van der Hoeven","year":"2021","unstructured":"van der Hoeven, J., Lecerf, G.: On the complexity exponent of polynomial system solving. Found. Comput. Math. 21, 1\u201357 (2021)","journal-title":"Found. Comput. Math."},{"key":"719_CR72","unstructured":"Van\u00a0der Hoeven, J., Lecerf, G.: Implementing number theoretic transforms. Technical Report, HAL, (2024). https:\/\/hal.science\/hal-04841449"},{"issue":"1","key":"719_CR73","first-page":"5","volume":"43","author":"J van der Hoeven","year":"2016","unstructured":"van der Hoeven, J., Lecerf, G., Quintin, G.: Modular SIMD arithmetic in Mathemagix. ACM Trans. Math. Softw. 43(1), 5\u20131 (2016)","journal-title":"ACM Trans. Math. Softw."},{"key":"719_CR74","unstructured":"Van\u00a0der Hoeven, J. et\u00a0al.: Mathemagix (2002) https:\/\/www.mathemagix.org"},{"key":"719_CR75","unstructured":"Intel corporation. Intel\u00ae 64 and IA-32 architectures software developer\u2019s manual. https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/articles\/technical\/intel-sdm.html"},{"issue":"3\/4","key":"719_CR76","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1145\/2576802.2576828","volume":"47","author":"F Johansson","year":"2014","unstructured":"Johansson, F.: Arb: a C library for ball arithmetic. ACM Commun. Comput. Algebra 47(3\/4), 166\u2013169 (2014)","journal-title":"ACM Commun. Comput. Algebra"},{"issue":"4","key":"719_CR77","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1109\/TC.2015.2441714","volume":"65","author":"M Jolde\u015f","year":"2015","unstructured":"Jolde\u015f, M., Marty, O., Muller, J.-M., Popescu, V.: Arithmetic algorithms for extended precision using floating-point expansions. IEEE Trans. Comput. 65(4), 1197\u20131210 (2015)","journal-title":"IEEE Trans. Comput."},{"key":"719_CR78","doi-asserted-by":"crossref","unstructured":"Joldes, M., Muller, J.-M., Popescu, V., Tucker, W.: CAMPARY: cuda multiple precision arithmetic library and applications. In Mathematical Software \u2013 ICMS 2016, pp. 232\u2013240. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-42432-3_29"},{"key":"719_CR79","unstructured":"Juliadiff: differentiation tools in Julia. https:\/\/juliadiff.org"},{"key":"719_CR80","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13, 1\u201346 (2004)","journal-title":"Comput. Complex."},{"issue":"3","key":"719_CR81","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","volume":"9","author":"E Kaltofen","year":"1990","unstructured":"Kaltofen, E., Trager, B.M.: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators. J. Symb. Comput. 9(3), 301\u2013320 (1990)","journal-title":"J. Symb. Comput."},{"key":"719_CR82","first-page":"595","volume":"7","author":"A Karatsuba","year":"1963","unstructured":"Karatsuba, A., Ofman, J.: Multiplication of multidigit numbers on automata. Soviet Physics Doklady 7, 595\u2013596 (1963)","journal-title":"Soviet Physics Doklady"},{"issue":"3","key":"719_CR83","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/0731048","volume":"31","author":"RB Kearfott","year":"1994","unstructured":"Kearfott, R.B.: An interval step control for continuation methods. SIAM J. Numer. Anal. 31(3), 892\u2013914 (1994)","journal-title":"SIAM J. Numer. Anal."},{"key":"719_CR84","doi-asserted-by":"crossref","unstructured":"Larrieu, R.: The truncated Fourier transform for mixed radices. In M.\u00a0Burr, editor, Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC \u201917, pp. 261\u2013268. New York, NY, USA (2017)","DOI":"10.1145\/3087604.3087636"},{"key":"719_CR85","doi-asserted-by":"crossref","unstructured":"Lecerf, G.: Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions. In Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201900, pages 209\u2013216. New York, NY, USA (2000)","DOI":"10.1145\/345542.345633"},{"key":"719_CR86","unstructured":"Lecerf, G.: Une alternative aux m\u00e9thodes de r\u00e9\u00e9criture pour la r\u00e9solution des syst\u00e8mes alg\u00e9briques. PhD thesis, \u00c9cole polytechnique (2001)"},{"issue":"6","key":"719_CR87","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s002000050115","volume":"9","author":"G Matera","year":"1999","unstructured":"Matera, G.: Probabilistic algorithms for geometric elimination. Appl. Algebra Engrg. Comm. Comput. 9(6), 463\u2013520 (1999)","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"issue":"262","key":"719_CR88","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1090\/S0025-5718-07-01956-4","volume":"77","author":"P Mih\u0103ilescu","year":"2008","unstructured":"Mih\u0103ilescu, P.: Fast convolutions meet montgomery. Math. Comp. 77(262), 1199\u20131221 (2008)","journal-title":"Math. Comp."},{"key":"719_CR89","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF01975722","volume":"5","author":"O M\u00f8ller","year":"1965","unstructured":"M\u00f8ller, O.: Quasi double-precision in floating point addition. BIT Numer. Math. 5, 37\u201350 (1965)","journal-title":"BIT Numer. Math."},{"key":"719_CR90","unstructured":"Montgomery, P.\u00a0L.: An FFT extension of the elliptic curve method of factorization. PhD thesis, University of California at Los Angeles (1992)"},{"key":"719_CR91","volume-title":"Interval Analysis","author":"RE Moore","year":"1966","unstructured":"Moore, R.E.: Interval Analysis. Prentice Hall, Englewood Cliffs, N.J (1966)"},{"key":"719_CR92","doi-asserted-by":"crossref","unstructured":"Moore, R.\u00a0E., Kearfott, R.\u00a0B., Cloud, M.\u00a0J.: Introduction to interval analysis. Soc. Ind. Appl. Math. (2009)","DOI":"10.1137\/1.9780898717716"},{"issue":"4","key":"719_CR93","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2017.v013a004","volume":"13","author":"CD Murray","year":"2017","unstructured":"Murray, C.D., Williams, R.R.: On the (non) NP-Hardness of computing circuit complexity. Theory of Comput. 13(4), 1\u201322 (2017)","journal-title":"Theory of Comput."},{"issue":"2","key":"719_CR94","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1147\/rd.222.0134","volume":"22","author":"HJ Nussbaumer","year":"1978","unstructured":"Nussbaumer, H.J., Quandalle, P.: Computation of convolutions and discrete Fourier transforms by polynomial transforms. IBM J. Res. Develop. 22(2), 134\u2013144 (1978)","journal-title":"IBM J. Res. Develop."},{"key":"719_CR95","unstructured":"LLVM ORC design and implementation. https:\/\/www.llvm.org\/docs\/ORCv2.html"},{"issue":"5","key":"719_CR96","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1145\/330249.330250","volume":"21","author":"M Poletto","year":"1999","unstructured":"Poletto, M., Sarkar, V.: Linear scan register allocation. ACM Trans. Program. Lang. Syst. 21(5), 895\u2013913 (1999)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"114","key":"719_CR97","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1090\/S0025-5718-1971-0301966-0","volume":"25","author":"JM Pollard","year":"1971","unstructured":"Pollard, J.M.: The fast Fourier transform in a finite field. Math. Comp. 25(114), 365\u2013374 (1971)","journal-title":"Math. Comp."},{"key":"719_CR98","volume-title":"Numerical recipes, the art of scientific computing","author":"WH Press","year":"2007","unstructured":"Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical recipes, the art of scientific computing, 3rd edn. Cambridge University Press, Cambridge (2007)","edition":"3"},{"key":"719_CR99","unstructured":"Priest, D.\u00a0M.: On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. PhD thesis, University of California at Berkeley (1992)"},{"key":"719_CR100","doi-asserted-by":"crossref","unstructured":"P\u00fcschel, M., Moura, J.\u00a0M.\u00a0F., Johnson, J., Padua, D., Veloso, M., Singer, B., Xiong, J., Franchetti, F., Gacic, A., Voronenko, Y., Chen, K., Johnson, R.\u00a0W., Rizzolo, N.: SPIRAL: code generation for DSP transforms. Proceedings of the IEEE, special issue on Program Generation, Optimization, and Adaptation, 93(2):232\u2013275 (2005)","DOI":"10.1109\/JPROC.2004.840306"},{"key":"719_CR101","doi-asserted-by":"crossref","unstructured":"Roche, D.\u00a0S.: What can (and can\u2019t) we do with sparse polynomials? In C.\u00a0Arreche, editor, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC \u201918, pages 25\u201330. New York, NY, USA (2018)","DOI":"10.1145\/3208976.3209027"},{"key":"719_CR102","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1017\/S096249291000005X","volume":"19","author":"SM Rump","year":"2010","unstructured":"Rump, S.M.: Verification methods: rigorous results using floating-point arithmetic. Acta Numer 19, 287\u2013449 (2010)","journal-title":"Acta Numer"},{"key":"719_CR103","unstructured":"Shoup, V.: NTL: a library for doing number theory (1996) www.shoup.net\/ntl"},{"issue":"3\u20134","key":"719_CR104","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3\u20134), 207\u2013388 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"719_CR105","first-page":"301","volume-title":"Introduction to numerical algebraic geometry","author":"AJ Sommese","year":"2005","unstructured":"Sommese, A.J., Verschelde, J., Wampler, C.W.: Introduction to numerical algebraic geometry, pp. 301\u2013337. Springer, Berlin (2005)"},{"key":"719_CR106","doi-asserted-by":"crossref","unstructured":"Takahashi, D.: An implementation of parallel number-theoretic transform using Intel AVX-512 instructions. In F.\u00a0Boulier, M.\u00a0England, T.\u00a0M.\u00a0Sadykov, and E.\u00a0V.\u00a0Vorozhtsov, editors, Computer Algebra in Scientific Computing. CASC 2022., volume 13366 of Lect. Notes Comput. Sci., pp. 318\u2013332. Springer, Cham (2022)","DOI":"10.1007\/978-3-031-14788-3_18"},{"issue":"2","key":"719_CR107","first-page":"714","volume":"4","author":"AL Toom","year":"1963","unstructured":"Toom, A.L.: The complexity of a scheme of functional elements realizing the multiplication of integers. Sov. Math. 4(2), 714\u2013716 (1963)","journal-title":"Sov. Math."}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-025-00719-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-025-00719-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-025-00719-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:07:19Z","timestamp":1776071239000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-025-00719-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":107,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["719"],"URL":"https:\/\/doi.org\/10.1007\/s00200-025-00719-0","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]},"assertion":[{"value":"20 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}