Inversion of circulant matrices over 𝐙ₘ
Dario A. Bini, Gianna M. Del Corso, Giovanni Manzini, Luciano Margara · Mathematics of Computation · 2000
In this paper we consider the problem of inverting an n × n n\times n circulant matrix with entries over Z m \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 Z m \mathbf {Z}_m . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of m m and n n , and their costs range, roughly, from n log n log log n n\log n\log \log n to n log 2 n log log n log m n \log ^2n\log \log n \log m operations over Z m \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.