Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\)
type: Item
instance of: scholarly article
title: Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\)
zbMATH Open document ID: 1020.65015
DOI: 10.1016/S0024-3795(02)00471-8
author: Carlo J. Accettella
author: Gianna M. Del Corso
author: Giovanni Manzini
published in: Linear Algebra and its Applications
publication date: 2003-05-25T00:00:00Z
review text: The authors consider the problem of inverting block circulant matrices with circulant blocks (BCCB) with entries over the field \({\mathbb{Z}_p}\). This problem has applications in the theory of two-dimensional linear cellular automata. Since the standard reduction to diagonal form by means of the fast Fourier transform has some drawbacks in \({\mathbb{Z}_p}\), the problem is solved by transforming it into the equivalent problem of inverting a circulant matrix with entries over a suitable ring \({\mathbb{R}}={\mathbb{Z}_p[y]}/a(y)\) in the cases the factorization of \(a(y)\) is known or unknown. It is shown that an \(m\times n\) BCCB matrix can be inverted in \(O(mnc(m,n))\) operations in \({\mathbb{Z}_p}\), where \(c\) is a low degree polynomial in \(\log m\) and \(\log n\). If \(n\) and \(m\) are powers of \(2\), the cost drops considerably.
reviewed by: Rémi Vaillancourt
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 15B33
zbMATH DE Number: 1915795
zbMATH Keywords: block circulant matrices
zbMATH Keywords: matrix inversion over finite fields
zbMATH Keywords: circulant matrices
zbMATH Keywords: extended Euclidean algorithm
zbMATH Keywords: linear cellular automata
zbMATH Keywords: reduction to diagonal form
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: factorization
MaRDI profile type: Publication
cites work: Inversion of circulant matrices over \(\mathbf{Z}_m\)
cites work: Q3208805
cites work: Exact results for deterministic cellular automata with additive rules
cites work: Q5653524
cites work: On the complexity of multiplication in finite fields
cites work: Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects
cites work: Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent
cites work: Modern computer algebra
description: scientific article; zbMATH DE number 1915795