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.

Inversion of Circulant Matrices over Zm

MANZINI, Giovanni;
2001-01-01

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11579/8866
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 13
social impact