let

be M sequences of length N (for each i in {0,...,M-1} there is a different sequence defined on {0,...,N-1}).

all the g's are smaller then N.

Now an operation F on any two sequences a,b on 0,..,N-1 , is defined to give a new sequence F(a,b) according to:

Now define recursively the following M sequences all of defined on{0,...,N-1}:

I need an efficient way for calculating the last sequence x(M-1).

If F was exactly the convolution of its two operands it would be easy - The FFT of x0 and all the y's are known analitically so i can multiply all of these FFT's in the frequency domain and transform back - only one IFFT is required! so this whole recursive calculation can be done in NlogN.

so is there a way to do this recursive operation entirely in the frequency domain?

thank you