Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\) (Q1874655): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:55, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\) |
scientific article |
Statements
Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\) (English)
0 references
25 May 2003
0 references
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.
0 references
block circulant matrices
0 references
matrix inversion over finite fields
0 references
circulant matrices
0 references
extended Euclidean algorithm
0 references
linear cellular automata
0 references
reduction to diagonal form
0 references
fast Fourier transform
0 references
factorization
0 references