We consider the problem of inverting block circulant with circulant blocks BCCB matrices with entries over the field $Zp$. This problem arises in the study of of two-dimensional linear cellular automata. Since the standard reduction to diagonal form by means of FFT has some drawbacks when working over $Zp$, we solve this problem by transforming it into the equivalent problem of inverting a circulant matrix with entries over a suitable ring~$R$. We show that a BCCB matrix of size $mn$ can be inverted in $O{m n, c(m,n)}$ operations in $Zp$, where $c$ is a low degree polynomial in $log m$ and $log n$.
展开▼
机译：我们考虑用循环块BCCB矩阵对块循环进行求逆的问题，该循环块BCCB矩阵的字段为$ Zp $。在二维线性细胞自动机的研究中出现了这个问题。由于在工作超过$ Zp $时，通过FFT将标准简化为对角线形式存在一些弊端，我们通过将其转换为等效的问题来解决这一问题，该问题是将带有合适环上的项的循环矩阵求逆。我们表明，大小为$ mn $的BCCB矩阵可以在$ Zp $中的$ O {mn，c（m，n）} $运算中求逆，其中$ c $是$ log m $和$ log中的低次多项式登录n $。
展开▼
