TY - JOUR
T1 - Inversion of two level circulant matrices over Zp
AU - Accettella, Carlo J.
AU - Del Corso, Gianna M.
AU - Manzini, Giovanni
PY - 2003/6/1
Y1 - 2003/6/1
N2 - 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.
AB - 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.
KW - Application of the extended Euclidean algorithm
KW - Block circulant matrices
KW - Circulant matrices over finite rings
KW - Matrix inversion over finite fields
UR - http://www.scopus.com/inward/record.url?scp=0037409930&partnerID=8YFLogxK
U2 - 10.1016/S0024-3795(02)00471-8
DO - 10.1016/S0024-3795(02)00471-8
M3 - Article
SN - 0024-3795
VL - 366
SP - 5
EP - 23
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
IS - SPEC. ISS.
ER -