{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:26Z","timestamp":1778065106129,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"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":[],"published-print":{"date-parts":[[2022,7,4]]},"DOI":"10.1145\/3476446.3535484","type":"proceedings-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T13:16:01Z","timestamp":1657026961000},"page":"409-418","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Faster Change of Order Algorithm for Gr\u00f6bner Bases under Shape and Stability Assumptions"],"prefix":"10.1145","author":[{"given":"J\u00e9r\u00e9my","family":"Berthomieu","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Neiger","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohab","family":"Safey El Din","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-018-9392-1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-87-05517-7"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings ISSAC 1994","author":"Becker E.","year":"1903","unstructured":"E. Becker , T. Mora , M.G. Marinari , and C. Traverso . 1994. The Shape of the Shape Lemma . In Proceedings ISSAC 1994 . ACM, 129--133. https:\/\/doi.org\/10.1145\/ 1903 47.190382 10.1145\/190347.190382 E. Becker, T. Mora, M.G. Marinari, and C. Traverso. 1994. The Shape of the Shape Lemma. In Proceedings ISSAC 1994. ACM, 129--133. https:\/\/doi.org\/10.1145\/190347.190382"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"T. Becker V. Weispfenning and H. Kredel. 1993. Gr\u00f6bner bases -- A computational approach to commutative algebra. Graduate texts in mathematics Vol. 141. Springer.  T. Becker V. Weispfenning and H. Kredel. 1993. Gr\u00f6bner bases -- A computational approach to commutative algebra. Graduate texts in mathematics Vol. 141. Springer.","DOI":"10.1007\/978-1-4612-0913-3_5"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2006.02.001"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2022.03.002"},{"key":"e_1_3_2_1_8_1","volume-title":"Safey El Din","author":"Berthomieu J.","year":"2021","unstructured":"J. Berthomieu , C. Eder , and M. Safey El Din . 2021 . Msolve : A Library for Solving Polynomial Systems . In Proceedings ISSAC 2021. ACM, 51--58. https:\/\/doi.org\/10\/gk8549 https:\/\/msolve.lip6.fr\/. J. Berthomieu, C. Eder, and M. Safey El Din. 2021. Msolve: A Library for Solving Polynomial Systems. In Proceedings ISSAC 2021. ACM, 51--58. https:\/\/doi.org\/10\/gk8549 https:\/\/msolve.lip6.fr\/."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1088216.1088219","article-title":"A Theoretical Basis for the Reduction of Polynomials to Canonical Forms","volume":"10","author":"Buchberger B.","year":"1976","unstructured":"B. Buchberger . 1976 . A Theoretical Basis for the Reduction of Polynomials to Canonical Forms . SIGSAM Bull. 10 , 3 (1976), 19 -- 29 . https:\/\/doi.org\/10\/d2cskd B. Buchberger. 1976. A Theoretical Basis for the Reduction of Polynomials to Canonical Forms. SIGSAM Bull. 10, 3 (1976), 19--29. https:\/\/doi.org\/10\/d2cskd","journal-title":"SIGSAM Bull."},{"key":"e_1_3_2_1_10_1","volume-title":"D. A. Cox, J. Little, and D. O'Shea. 2007. Ideals, Varieties, and Algorithms","unstructured":"D. A. Cox, J. Little, and D. O'Shea. 2007. Ideals, Varieties, and Algorithms ( third edition). Springer-Verlag New-York . https:\/\/doi.org\/10.1007\/978-0--387--35651--8 10.1007\/978-0--387--35651--8 D. A. Cox, J. Little, and D. O'Shea. 2007. Ideals, Varieties, and Algorithms (third edition). Springer-Verlag New-York. https:\/\/doi.org\/10.1007\/978-0--387--35651--8"},{"key":"e_1_3_2_1_11_1","unstructured":"D. S. Dummit and R. M. Foote. 2004. Abstract algebra (3rd ed.). Wiley.  D. S. Dummit and R. M. Foote. 2004. Abstract algebra (3rd ed.). Wiley."},{"key":"e_1_3_2_1_12_1","volume-title":"Commutative Algebra: with a View Toward Algebraic Geometry","author":"Eisenbud D.","unstructured":"D. Eisenbud . 1995. Commutative Algebra: with a View Toward Algebraic Geometry . Springer . https:\/\/doi.org\/10.1007\/978--1--4612--5350--1 10.1007\/978--1--4612--5350--1 D. Eisenbud. 1995. Commutative Algebra: with a View Toward Algebraic Geometry. Springer. https:\/\/doi.org\/10.1007\/978--1--4612--5350--1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(99)00005-5"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/780506.780516"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings ISSAC","author":"Faug\u00e8re J.-C.","year":"2014","unstructured":"J.-C. Faug\u00e8re , P. Gaudry , L. Huot , and G. Renault . 2014. Sub-Cubic Change of Ordering for Gr\u00f6bner Basis: A Probabilistic Approach . In Proceedings ISSAC 2014 . ACM, 170--177. https:\/\/doi.org\/10.1145\/2608628.2608669 10.1145\/2608628.2608669 J.-C. Faug\u00e8re, P. Gaudry, L. Huot, and G. Renault. 2014. Sub-Cubic Change of Ordering for Gr\u00f6bner Basis: A Probabilistic Approach. In Proceedings ISSAC 2014. ACM, 170--177. https:\/\/doi.org\/10.1145\/2608628.2608669"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1993.1051"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings ISSAC","author":"Faug\u00e8re J.-C.","year":"2011","unstructured":"J.-C. Faug\u00e8re and C. Mou . 2011. Fast Algorithm for Change of Ordering of Zerodimensional Gr\u00f6bner Bases with Sparse Multiplication Matrices . In Proceedings ISSAC 2011 . ACM, 115--122. https:\/\/doi.org\/10\/fhhs56 J.-C. Faug\u00e8re and C. Mou. 2011. Fast Algorithm for Change of Ordering of Zerodimensional Gr\u00f6bner Bases with Sparse Multiplication Matrices. In Proceedings ISSAC 2011. ACM, 115--122. https:\/\/doi.org\/10\/fhhs56"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2016.07.025"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings ISSAC","author":"Ferguson A.","year":"2022","unstructured":"A. Ferguson and H.P. Le . 2022. Finer complexity estimates for the change of ordering of Gr\u00f6bner bases for generic symmetric determinantal ideals . In Proceedings ISSAC 2022 . ACM. https:\/\/doi.org\/10.1145\/3476446.3536182 10.1145\/3476446.3536182 A. Ferguson and H.P. Le. 2022. Finer complexity estimates for the change of ordering of Gr\u00f6bner bases for generic symmetric determinantal ideals. In Proceedings ISSAC 2022. ACM. https:\/\/doi.org\/10.1145\/3476446.3536182"},{"key":"e_1_3_2_1_20_1","volume-title":"Fonctions de Plusieurs Variables Complexes","author":"Galligo A.","unstructured":"A. Galligo . 1974. \u00c0 propos du th\u00e9or\u00e8me de pr\u00e9paration deWeierstrass . In Fonctions de Plusieurs Variables Complexes . Springer Berlin Heidelberg , 543--579. https: \/\/doi.org\/10.1007\/BFb0068121 10.1007\/BFb0068121 A. Galligo. 1974. \u00c0 propos du th\u00e9or\u00e8me de pr\u00e9paration deWeierstrass. In Fonctions de Plusieurs Variables Complexes. Springer Berlin Heidelberg, 543--579. https: \/\/doi.org\/10.1007\/BFb0068121"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings AAECC","author":"Gianni P.","year":"1987","unstructured":"P. Gianni and T. Mora . 1989. Algebraic solution of systems of polynomial equations using Groebner bases . In Proceedings AAECC 1987 . Springer, 247--257. https:\/\/doi.org\/10.1007\/3--540--51082--6_83 10.1007\/3--540--51082--6_83 P. Gianni and T. Mora. 1989. Algebraic solution of systems of polynomial equations using Groebner bases. In Proceedings AAECC 1987. Springer, 247--257. https:\/\/doi.org\/10.1007\/3--540--51082--6_83"},{"key":"e_1_3_2_1_22_1","volume-title":"Hermite forms of polynomial matrices. Master's thesis","author":"Gupta S.","unstructured":"S. Gupta . 2011. Hermite forms of polynomial matrices. Master's thesis . University of Waterloo , Canada. S. Gupta. 2011. Hermite forms of polynomial matrices. Master's thesis. University of Waterloo, Canada."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.09.006"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings ISSAC 2011","author":"Gupta S.","year":"1993","unstructured":"S. Gupta and A. Storjohann . 2011. Computing Hermite Forms of Polynomial Matrices . In Proceedings ISSAC 2011 . ACM, 155--162. https:\/\/doi.org\/10.1145\/ 1993 886.1993913 S. Gupta and A. Storjohann. 2011. Computing Hermite Forms of Polynomial Matrices. In Proceedings ISSAC 2011. ACM, 155--162. https:\/\/doi.org\/10.1145\/ 1993886.1993913"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1851.41.191"},{"key":"#cr-split#-e_1_3_2_1_26_1.1","doi-asserted-by":"crossref","unstructured":"J. Herzog and T. Hibi. 2011. Monomial Ideals. Springer London. 3--22 pages. https:\/\/doi.org\/10.1007\/978-0--85729--106--6 10.1007\/978-0--85729--106--6","DOI":"10.1007\/978-0-85729-106-6_1"},{"key":"#cr-split#-e_1_3_2_1_26_1.2","doi-asserted-by":"crossref","unstructured":"J. Herzog and T. Hibi. 2011. Monomial Ideals. Springer London. 3--22 pages. https:\/\/doi.org\/10.1007\/978-0--85729--106--6","DOI":"10.1007\/978-0-85729-106-6_1"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.07.010"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326229.3326272"},{"key":"e_1_3_2_1_29_1","volume-title":"Linear Systems","author":"Kailath T.","unstructured":"T. Kailath . 1980. Linear Systems . Prentice-Hall . T. Kailath. 1980. Linear Systems. Prentice-Hall."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2007.06.004"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"M. Kreuzer and L. Robbiano. 2016. Computational linear and commutative algebra. Springer.  M. Kreuzer and L. Robbiano. 2016. Computational linear and commutative algebra. Springer.","DOI":"10.1007\/978-3-319-43601-2"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.03.003"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(85)80035-3"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386834"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(02)00297-9"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101572"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101502"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings ISSAC","author":"Pernet C.","year":"2007","unstructured":"C. Pernet and A. Storjohann . 2007. Faster Algorithms for the Characteristic Polynomial . In Proceedings ISSAC 2007 . ACM, 307--314. https:\/\/doi.org\/10\/fcdnsm C. Pernet and A. Storjohann. 2007. Faster Algorithms for the Characteristic Polynomial. In Proceedings ISSAC 2007. ACM, 307--314. https:\/\/doi.org\/10\/fcdnsm"},{"key":"e_1_3_2_1_40_1","unstructured":"C. Pernet and A. Storjohann. 2007. Frobenius form in expected matrix multiplication time over sufficiently large fields. Unpublished report. https:\/\/cs.uwaterloo.ca\/~astorjoh\/cpoly.pdf  C. Pernet and A. Storjohann. 2007. Frobenius form in expected matrix multiplication time over sufficiently large fields. Unpublished report. https:\/\/cs.uwaterloo.ca\/~astorjoh\/cpoly.pdf"},{"key":"e_1_3_2_1_41_1","unstructured":"L. Perret. 2016. Bases de Gr\u00f6bner en Cryptographie Post-Quantique. Habilitation \u00e0 diriger des recherches. UPMC - Paris 6 Sorbonne Universit\u00e9s. https:\/\/tel.archivesouvertes. fr\/tel-01417808  L. Perret. 2016. Bases de Gr\u00f6bner en Cryptographie Post-Quantique. Habilitation \u00e0 diriger des recherches. UPMC - Paris 6 Sorbonne Universit\u00e9s. https:\/\/tel.archivesouvertes. fr\/tel-01417808"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0310020"},{"key":"e_1_3_2_1_43_1","volume-title":"NTL: A library for doing number theory, version 11.5.1. https:\/\/libntl.org.","author":"Shoup V.","year":"2021","unstructured":"V. Shoup . 2021 . NTL: A library for doing number theory, version 11.5.1. https:\/\/libntl.org. V. Shoup. 2021. NTL: A library for doing number theory, version 11.5.1. https:\/\/libntl.org."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2790282.2791392"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"B. Sturmfels. 2002. Solving systems of polynomial equations. Number 97. American Mathematical Soc.  B. Sturmfels. 2002. Solving systems of polynomial equations. Number 97. American Mathematical Soc.","DOI":"10.1090\/cbms\/097"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208976.3209020"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"e_1_3_2_1_49_1","volume-title":"Proceedings ISSAC","author":"Zhou W.","year":"2013","unstructured":"W. Zhou and G. Labahn . 2013. Computing Column Bases of Polynomial Matrices . In Proceedings ISSAC 2013 . ACM, 379--386. https:\/\/doi.org\/10.1145\/2465506.2465947 10.1145\/2465506.2465947 W. Zhou and G. Labahn. 2013. Computing Column Bases of Polynomial Matrices. In Proceedings ISSAC 2013. ACM, 379--386. https:\/\/doi.org\/10.1145\/2465506.2465947"},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings ISSAC","author":"Zhou W.","year":"2012","unstructured":"W. Zhou , G. Labahn , and A. Storjohann . 2012. Computing Minimal Nullspace Bases . In Proceedings ISSAC 2012 . ACM, 366--373. https:\/\/doi.org\/10.1145\/2442829.2442881 10.1145\/2442829.2442881 W. Zhou, G. Labahn, and A. Storjohann. 2012. Computing Minimal Nullspace Bases. In Proceedings ISSAC 2012. ACM, 366--373. https:\/\/doi.org\/10.1145\/2442829.2442881"}],"event":{"name":"ISSAC '22: International Symposium on Symbolic and Algebraic Computation","location":"Villeneuve-d'Ascq France","acronym":"ISSAC '22","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"]},"container-title":["Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3535484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476446.3535484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:47Z","timestamp":1750188647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3535484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":48,"alternative-id":["10.1145\/3476446.3535484","10.1145\/3476446"],"URL":"https:\/\/doi.org\/10.1145\/3476446.3535484","relation":{},"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"2022-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}