In this paper we consider the problem of inverting an n x 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). 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. [References: 16]
展开▼
机译：在本文中，我们考虑了将项Z（m）上的n x n循环矩阵求逆的问题。我们表明，基于FFT变换为对角线形式的循环量反演算法在Z（m）上工作时存在一些缺点。我们提出了三种不使用这种方法的不同算法。我们的算法需要对m和n有不同程度的了解，并且它们的成本范围大约为n log n log log n到n log（2）n log log n log m对Z（m）的操作。此外，对于每种算法，我们以位运算的方式给出成本。我们还提出了一种用于有限生成的双无限Toeplitz矩阵求逆的算法。本文考虑的问题已应用于线性元胞自动机理论。 [参考：16]
展开▼
