Inversion of two level circulant matrices over Zp

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

doi:10.1016/S0024-3795(02)00471-8

Inversion of two level circulant matrices over Z_p

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

Research output: Contribution to journal › Article › peer-review

Abstract

We consider the problem of inverting block circulant with circulant blocks (BCCB) matrices with entries over the field Z_p. 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 Z_p, 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 Z_p, where c is a low degree polynomial in log m and log n.

Original language	English
Pages (from-to)	5-23
Number of pages	19
Journal	Linear Algebra and Its Applications
Volume	366
Issue number	SPEC. ISS.
DOIs	https://doi.org/10.1016/S0024-3795(02)00471-8
Publication status	Published - 1 Jun 2003
Externally published	Yes

Keywords

Application of the extended Euclidean algorithm
Block circulant matrices
Circulant matrices over finite rings
Matrix inversion over finite fields

Access to Document

10.1016/S0024-3795(02)00471-8

Cite this

@article{e9d9f1df67144185a747e8d6a0aa2625,

title = "Inversion of two level circulant matrices over Zp ",

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.",

keywords = "Application of the extended Euclidean algorithm, Block circulant matrices, Circulant matrices over finite rings, Matrix inversion over finite fields",

author = "Accettella, \{Carlo J.\} and \{Del Corso\}, \{Gianna M.\} and Giovanni Manzini",

year = "2003",

month = jun,

day = "1",

doi = "10.1016/S0024-3795(02)00471-8",

language = "English",

volume = "366",

pages = "5--23",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "SPEC. ISS.",

}

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 - https://www.scopus.com/pages/publications/0037409930

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 -

Inversion of two level circulant matrices over Z_p

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this