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?)

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