Inversion of two level circulant matrices over Zp

Carlo J. Accettella, Gianna M. Del Corso, Giovanni Manzini

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

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(mn c(m,n)) operations in Zp, where c is a low degree polynomial in log m and log n.

Lingua originaleInglese
pagine (da-a)5-23
Numero di pagine19
RivistaLinear Algebra and Its Applications
Volume366
Numero di pubblicazioneSPEC. ISS.
DOI
Stato di pubblicazionePubblicato - 1 giu 2003
Pubblicato esternamente

Fingerprint

Entra nei temi di ricerca di 'Inversion of two level circulant matrices over Zp'. Insieme formano una fingerprint unica.

Cita questo