Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\) (Q1874655)

The authors consider the problem of inverting block circulant matrices with circulant blocks (BCCB) with entries over the field \({\mathbb{Z}_p}\). This problem has applications in the theory of two-dimensional linear cellular automata. Since the standard reduction to diagonal form by means of the fast Fourier transform has some drawbacks in \({\mathbb{Z}_p}\), the problem is solved by transforming it into the equivalent problem of inverting a circulant matrix with entries over a suitable ring \({\mathbb{R}}={\mathbb{Z}_p[y]}/a(y)\) in the cases the factorization of \(a(y)\) is known or unknown. It is shown that an \(m\times n\) BCCB matrix can be inverted in \(O(mnc(m,n))\) operations in \({\mathbb{Z}_p}\), where \(c\) is a low degree polynomial in \(\log m\) and \(\log n\). If \(n\) and \(m\) are powers of \(2\), the cost drops considerably.