Inversion of circulant matrices over Z

In this paper we consider the problem of inverting an n × n circulant matrix with entries over Z. 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 Z. 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 n log log n log m operations over Z. 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.