PUMA
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.
 
 
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


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