Inversion of circulant matrices over ![]() |
| |
Authors: | Dario Bini Gianna M Del Corso Giovanni Manzini Luciano Margara |
| |
Institution: | Dipartimento di Matematica, Università di Pisa, Pisa, Italy ; Istituto di Matematica Computazionale-CNR, Pisa, Italy ; Dip. Scienze e Tecnologie Avanzate, Università del Piemonte Orientale, and IMC-CNR, Pisa, Italy ; Dipartimento di Informatica, Università di Bologna, Bologna, Italy |
| |
Abstract: | In this paper we consider the problem of inverting an circulant matrix with entries over . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of and , and their costs range, roughly, from to operations over . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata. |
| |
Keywords: | Circulant matrices bi-infinite Toeplitz matrices inversion over rings Laurent series |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|