Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
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

Abstract:

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
Email: bini@dm.unipi.it

Gianna M. Del Corso
Affiliation: Istituto di Matematica Computazionale-CNR, Pisa, Italy
Email: delcorso@imc.pi.cnr.it

Giovanni Manzini
Affiliation: Dip. Scienze e Tecnologie Avanzate, Università del Piemonte Orientale, and IMC-CNR, Pisa, Italy
Email: manzini@mfn.unipmn.it

Luciano Margara
Affiliation: Dipartimento di Informatica, Università di Bologna, Bologna, Italy
Email: margara@cs.unibo.it

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01235-7
PII: S 0025-5718(00)01235-7
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