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$.
Inversion of two level Circulant Matrices over Zp
2003
Abstract
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$.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
