Real factorisation of noncyclic-convolution operators with application to fast convolution

Abstract

A real factorisation of discrete noncyclic-convolution operators is established which yields a fast procedure for performing noncyclic convolutions. The transformations associated with the factorisation need only real summations and subtractions for evaluation purposes, unlike the fast Fourier transform but like the fast Walsh transform.