Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Inversion of circulant matrices over $\mathbf{Z}_m$

Authors: Dario Bini, Gianna M. Del Corso, Giovanni Manzini and Luciano Margara
Journal: Math. Comp. 70 (2001), 1169-1182
MSC (2000): Primary 15A33, 65F05
Published electronically: March 24, 2000
MathSciNet review: 1710660
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


In this paper we consider the problem of inverting an $n\times n$ circulant matrix with entries over $\mathbf{Z}_m$. 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 $\mathbf{Z}_m$. We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of $m$ and $n$, and their costs range, roughly, from $n\log n\log\log n$ to $n \log^2n\log\log n \log m$ operations over $\mathbf{Z}_m$. 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.

References [Enhancements On Off] (What's this?)

  • 1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachussets, 1974. MR 54:1706
  • 2. D. Bini and V. Y. Pan. Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms. Birkhäuser, 1994. MR 95k:65003
  • 3. P. Chaudhuri, D. Chowdhury, S. Nandi, and S. Chattopadhyay. Additive Cellular Automata Theory and Applications, Vol. 1. IEEE Press, 1997.
  • 4. H. Cohen. A course in computational algebraic number theory, Volume 138 of Graduate Texts in Mathematics. Springer-Verlag, 1993. MR 94i:11105
  • 5. P. Feinsilver. Circulants, inversion of circulants, and some related matrix algebras. Linear Algebra and Appl., 56 (1984), 29-43. MR 85e:15005
  • 6. P. Guan and Y. He. Exact results for deterministic cellular automata with additive rules. Jour. Stat. Physics, 43 (1986), 463-478. MR 87j:68087
  • 7. A. S. Householder. The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill, New York, 1970. MR 52:9593
  • 8. M. Ito, N. Osato, and M. Nasu. Linear cellular automata over ${Z}_m$. Journal of Computer and System Sciences, 27 (1983), 125-140. MR 85f:68074
  • 9. A. Lempel, G. Seroussi, and S. Winograd. On the complexity of multiplication in finite fields. Theoretical Computer Science, 22(3) (1983), 285-296. MR 84c:68031
  • 10. 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. CMP 92:01
  • 11. G. Manzini and L. Margara. A complete and efficiently computable topological classification of ${D}$-dimensional linear cellular automata over ${Z}_m$. Theoretical Computer Science, 221(2) (1999), 157-177. CMP 99:16
  • 12. G. Manzini and L. Margara. Invertible linear cellular automata over ${Z}_m$: Algorithmic and dynamical aspects. Journal of Computer and System Sciences, 56 (1998), 60-67. MR 99j:68089
  • 13. O. Martin, A. Odlyzko, and S. Wolfram. Algebraic properties of cellular automata. Comm. Math. Phys., 93 (1984), 219-258. MR 86a:68073
  • 14. A. M. Ostrowski. Recherches sur la méthode de Graeffe et les zéros des polynomes et des series de Laurent. Acta Math., 72 (1940), 99-257. MR 2:342c
  • 15. A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing, 7 (1971), 281-292. MR 45:1431
  • 16. S. Takahashi. Self-similarity of linear cellular automata. Journal of Computer and System Sciences, 44(1) (1992), 114-140. MR 94b:58058

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 15A33, 65F05

Retrieve articles in all journals with MSC (2000): 15A33, 65F05

Additional Information

Dario Bini
Affiliation: Dipartimento di Matematica, Università di Pisa, Pisa, Italy

Gianna M. Del Corso
Affiliation: Istituto di Matematica Computazionale-CNR, Pisa, Italy

Giovanni Manzini
Affiliation: Dip. Scienze e Tecnologie Avanzate, Università del Piemonte Orientale, and IMC-CNR, Pisa, Italy

Luciano Margara
Affiliation: Dipartimento di Informatica, Università di Bologna, Bologna, Italy

Keywords: Circulant matrices, bi-infinite Toeplitz matrices, inversion over rings, Laurent series
Received by editor(s): December 17, 1998
Received by editor(s) in revised form: June 28, 1999
Published electronically: March 24, 2000
Additional Notes: The first author was supported by Progetto Coordinato GNIM-CNR Toeplitz-like matrices: structures algorithms and applications.
A preliminary version of this paper has been presented to the 25th International Colloquium on Automata, Languages and Programming (ICALP ’98)
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society