Istituto di Informatica e Telematica     
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.
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

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional