{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T09:20:46Z","timestamp":1758705646306,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,14]],"date-time":"2023-10-14T00:00:00Z","timestamp":1697241600000},"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 Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix\n            <jats:italic>A<\/jats:italic>\n            of dimension\n            <jats:italic>n<\/jats:italic>\n            . The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by\n            <jats:italic>\n              O(n\n              <jats:sup>3<\/jats:sup>\n            <\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            + log ||A||)\n            <jats:sup>2<\/jats:sup>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            ) bit operations, where ||\n            <jats:italic>A<\/jats:italic>\n            ||= max\n            <jats:sub>\n              <jats:italic>ij<\/jats:italic>\n            <\/jats:sub>\n            |\n            <jats:italic>\n              A\n              <jats:sub>ij<\/jats:sub>\n            <\/jats:italic>\n            | denotes the largest entry of\n            <jats:italic>A<\/jats:italic>\n            in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time\n            <jats:italic>\n              (n\n              <jats:sup>3<\/jats:sup>\n            <\/jats:italic>\n            log ||\n            <jats:italic>A<\/jats:italic>\n            ||)\n            <jats:sup>\n              1+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            bit operations, where the exponent \u201c\n            <jats:italic>+ o<\/jats:italic>\n            (1)\u201d captures additional factors\n            <jats:italic>\n              c\n              <jats:sub>1<\/jats:sub>\n            <\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>c2<\/jats:sup>\n            (loglog||\n            <jats:italic>A<\/jats:italic>\n            ||)\n            <jats:sup>c3<\/jats:sup>\n            for positive real constants\n            <jats:italic>\n              c\n              <jats:sub>1<\/jats:sub>\n              ,c\n              <jats:sub>2<\/jats:sub>\n              ,c\n              <jats:sub>3<\/jats:sub>\n            <\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3617996","type":"journal-article","created":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T11:14:20Z","timestamp":1693480460000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Cubic Algorithm\u00a0for Computing the Hermite Normal Form of a Nonsingular Integer Matrix"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1766-9814","authenticated-orcid":false,"given":"Stavros","family":"Birmpilis","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-8977-4890","authenticated-orcid":false,"given":"George","family":"Labahn","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6354-8810","authenticated-orcid":false,"given":"Arne","family":"Storjohann","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,14]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_1_3_1","volume-title":"Efficient Algorithms","author":"Bach E.","year":"1996","unstructured":"E. Bach and J. Shallit . 1996 . Algorithmic Number Theory , volume 1 : Efficient Algorithms . MIT Press . E. Bach and J. Shallit. 1996. Algorithmic Number Theory, volume 1: Efficient Algorithms. MIT Press."},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892230031"},{"volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC\u201999)","author":"Beckermann B.","key":"e_1_3_1_5_1","unstructured":"B. Beckermann , G. Labahn , and G. Villard . 1999. Shifted normal forms of polynomial matrices . In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC\u201999) , S. Dooley (Ed.). ACM Press, New York, 189\u2013196. B. Beckermann, G. Labahn, and G. Villard. 1999. Shifted normal forms of polynomial matrices. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC\u201999), S. Dooley (Ed.). ACM Press, New York, 189\u2013196."},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation: ISSAC\u201920","author":"Birmpilis S.","key":"e_1_3_1_6_1","unstructured":"S. Birmpilis , G. Labahn , and A. Storjohann . 2020. A Las Vegas algorithm for computing the Smith form of a nonsingular integer matrix . In Proceedings International Symposium on Symbolic and Algebraic Computation: ISSAC\u201920 , New York, NY, USA, ACM, 38\u201345. S. Birmpilis, G. Labahn, and A. Storjohann. 2020. A Las Vegas algorithm for computing the Smith form of a nonsingular integer matrix. In Proceedings International Symposium on Symbolic and Algebraic Computation: ISSAC\u201920, New York, NY, USA, ACM, 38\u201345."},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2022.09.002"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211057"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.1.50"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-1002631-0"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2021.193.2.4"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1851.41.191"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081088608817705"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9165-9"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218045"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208040"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.03.003"},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201919)","author":"Liu R.","key":"e_1_3_1_19_1","unstructured":"R. Liu and Y. Pan . 2019. Computing Hermite normal form faster via solving system of linear equations . In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201919) . ACM, New York, NY, 283\u2013290. R. Liu and Y. Pan. 2019. Computing Hermite normal form faster via solving system of linear equations. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201919). ACM, New York, NY, 283\u2013290."},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201901)","author":"Micciancio D.","key":"e_1_3_1_20_1","unstructured":"D. Micciancio and B. Warinschi . 2001. A linear space algorithm for computing the Hermite normal form . In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201901) . B. Mourrain (Ed.), ACM Press, New York, NY, 231\u2014236. D. Micciancio and B. Warinschi. 2001. A linear space algorithm for computing the Hermite normal form. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201901). B. Mourrain (Ed.), ACM Press, New York, NY, 231\u2014236."},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201913)","author":"Pauderis C.","key":"e_1_3_1_21_1","unstructured":"C. Pauderis and A. Storjohann . 2013. Computing the invariant structure of integer matrices: Fast algorithms into practice . In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201913) . ACM, New York, NY, 307\u2013314. C. Pauderis and A. Storjohann. 2013. Computing the invariant structure of integer matrices: Fast algorithms into practice. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201913). ACM, New York, NY, 307\u2013314."},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2010.01.017"},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","key":"e_1_3_1_23_1","unstructured":"A. Schrijver . 1998. Theory of Linear and Integer Programming . John Wiley & Sons . A. Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons."},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0106-7"},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201996)","author":"Storjohann A.","key":"e_1_3_1_26_1","unstructured":"A. Storjohann and G. Labahn . 1996. Asymptotically fast computation of Hermite normal forms of integer matrices . In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201996) , Y. N. Lakshman (Ed.). ACM Press, New York, NY, 259\u2013266. A. Storjohann and G. Labahn. 1996. Asymptotically fast computation of Hermite normal forms of integer matrices. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201996), Y. N. Lakshman (Ed.). ACM Press, New York, NY, 259\u2013266."},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201998)","author":"Storjohann A.","key":"e_1_3_1_27_1","unstructured":"A. Storjohann and T. Mulders . 1998. Fast algorithms for linear algebra modulo N . In Proceedings of the European Symposium on Algorithms (ESA\u201998) , G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci (Eds.), LNCS 1461, Springer Verlag, Berlin, 139\u2013150. A. Storjohann and T. Mulders. 1998. Fast algorithms for linear algebra modulo N. In Proceedings of the European Symposium on Algorithms (ESA\u201998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci (Eds.), LNCS 1461, Springer Verlag, Berlin, 139\u2013150."},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.12.009"},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201913)","author":"Zhou W.","key":"e_1_3_1_29_1","unstructured":"W. Zhou and G. Labahn . 2013. Computing column bases of polynomial matrices . In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201913) . ACM Press, Boston, MA, 379\u2013388. W. Zhou and G. Labahn. 2013. Computing column bases of polynomial matrices. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201913). ACM Press, Boston, MA, 379\u2013388."},{"volume-title":"Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201912)","author":"Zhou W.","key":"e_1_3_1_30_1","unstructured":"W. Zhou , G. Labahn , and A. Storjohann . 2012. Computing minimal nullspace basis . In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201912) , J. van der Hoeven and M. van Hoeij (Eds.), ACM Press, New York, NY, 366\u2013373. W. Zhou, G. Labahn, and A. Storjohann. 2012. Computing minimal nullspace basis. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC\u201912), J. van der Hoeven and M. van Hoeij (Eds.), ACM Press, New York, NY, 366\u2013373."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617996","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617996","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:58Z","timestamp":1750178278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617996"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,14]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3617996"],"URL":"https:\/\/doi.org\/10.1145\/3617996","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,10,14]]},"assertion":[{"value":"2022-09-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}