Análisis y diseño de algoritmos para la computación con estructuras circulantes

Abstract

This dissertation proposal deals with the study of algorithms for computation with circulants structures. We study the different current algorithms for computation with circulant structures; specifically, for sequence convolutions and polynomial multiplications. Particularly, this work focuses on the arithmetic complexity of the matrix-vector product computations when they represent cyclic convolution operations in order to obtain efficient algorithms with low complexity in the multiplication sense.

Actually, two threads are used for the computation of the cyclic convolution: the direct approach which examines the structure of the system of equations describing the convolution operation, and the transform approach which maps the convolution operation into an alternative domain using the discrete Fourier transform (DFT) as tool.

We present an eclectic approach, using the intrinsic symmetry of the circulant matrices, and the roots of units of the monic polynomial z^N -1, for the formulation of new algorithms for the cyclic convolution and for the products of polynomials of order N=2^S with s belonging to the positive whole numbers (sEZ+), which reach low multiplicative complexity, according to Winograd’s theorem.