Inversion of Circulant Matrices over Z_m

摘要

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