Manzini G. Inversion of two level Circulant Matrices over Zp. In: LINEAR ALGEBRA AND ITS APPLICATIONS (65219J0), vol. 366 pp. 5 - 23. Science Direc t, 2003. |

Abstract (English) |
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$. | |

Subject | Block circulant matrices Matrix inversion over finite fields G.1 NUMERICAL ANALYSIS |

1) Download Document PDF |

Open access Restricted Private