{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T02:52:34Z","timestamp":1776826354005,"version":"3.51.2"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"235","license":[{"start":{"date-parts":[[2001,3,24]],"date-time":"2001-03-24T00:00:00Z","timestamp":985392000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In this paper we consider the problem of inverting an\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n times n\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\n                              \u00d7\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n\\times n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    circulant matrix with entries over\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"bold upper Z Subscript m\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"bold\">Z<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbf {Z}_m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"bold upper Z Subscript m\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"bold\">Z<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbf {Z}_m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"m\">\n                        <mml:semantics>\n                          <mml:mi>m<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , and their costs range, roughly, from\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n log n log log n\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n\\log n\\log \\log n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n log squared n log log n log m\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n \\log ^2n\\log \\log n \\log m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    operations over\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"bold upper Z Subscript m\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"bold\">Z<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbf {Z}_m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata.\n                  <\/p>","DOI":"10.1090\/s0025-5718-00-01235-7","type":"journal-article","created":{"date-parts":[[2002,11,6]],"date-time":"2002-11-06T14:02:22Z","timestamp":1036591342000},"page":"1169-1182","source":"Crossref","is-referenced-by-count":24,"title":["Inversion of circulant matrices over \ud835\udc19\u2098"],"prefix":"10.1090","volume":"70","author":[{"given":"Dario","family":"Bini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianna","family":"Del Corso","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciano","family":"Margara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"1","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The design and analysis of computer algorithms","author":"Aho, Alfred V.","year":"1975"},{"key":"2","series-title":"Progress in Theoretical Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3","volume-title":"Polynomial and matrix computations. Vol. 1","author":"Bini, Dario","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0817637869"},{"key":"3","unstructured":"P. Chaudhuri, D. Chowdhury, S. Nandi, and S. Chattopadhyay. Additive Cellular Automata Theory and Applications, Vol. 1. IEEE Press, 1997."},{"key":"4","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0024-3795(84)90111-3","article-title":"Circulants, inversion of circulants, and some related matrix algebras","volume":"56","author":"Feinsilver, Philip","year":"1984","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"3-4","key":"6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01020648","article-title":"Exact results for deterministic cellular automata with additive rules","volume":"43","author":"Guan, Puhua","year":"1986","journal-title":"J. Statist. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4715","issn-type":"print"},{"key":"7","series-title":"International Series in Pure and Applied Mathematics","volume-title":"The numerical treatment of a single nonlinear equation","author":"Householder, A. S.","year":"1970"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0022-0000(83)90033-8","article-title":"Linear cellular automata over \ud835\udc4d\u2098","volume":"27","author":"It\u00f4, Masanobu","year":"1983","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0304-3975(83)90108-1","article-title":"On the complexity of multiplication in finite fields","volume":"22","author":"Lempel, A.","year":"1983","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"10","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra and H. W. Lenstra. Algorithms in number theory, In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity. The MIT Press\/Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50017-5"},{"key":"11","doi-asserted-by":"crossref","unstructured":"G. Manzini and L. Margara. A complete and efficiently computable topological classification of \ud835\udc37-dimensional linear cellular automata over \ud835\udc4d\u2098. Theoretical Computer Science, 221(2) (1999), 157\u2013177.","DOI":"10.1016\/S0304-3975(99)00031-6"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1006\/jcss.1997.1535","article-title":"Invertible linear cellular automata over \ud835\udc4d\u2098: algorithmic and dynamical aspects","volume":"56","author":"Manzini, Giovanni","year":"1998","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"issue":"2","key":"13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01223745","article-title":"Algebraic properties of cellular automata","volume":"93","author":"Martin, Olivier","year":"1984","journal-title":"Comm. Math. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-3616","issn-type":"print"},{"key":"14","volume-title":"New First Course in the Theory of Equations","author":"Dickson, Leonard Eugene","year":"1939"},{"key":"15","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/0022-0000(92)90007-6","article-title":"Self-similarity of linear cellular automata","volume":"44","author":"Takahashi, Satoshi","year":"1992","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-235\/S0025-5718-00-01235-7\/S0025-5718-00-01235-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-235\/S0025-5718-00-01235-7\/S0025-5718-00-01235-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:41:41Z","timestamp":1776724901000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-235\/S0025-5718-00-01235-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3,24]]},"references-count":16,"journal-issue":{"issue":"235","published-print":{"date-parts":[[2001,7]]}},"alternative-id":["S0025-5718-00-01235-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01235-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3,24]]}}}