Summary: We consider the problem of inverting an \(n\times n\) circulant matrix with entries over \(\mathbb{Z}_m\). We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of the fast Fourier transform, has some drawbacks when working over \(\mathbb{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 \(\mathbb{Z}_m\). 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.
For the entire collection see [Zbl 0893.00039].