[amelius]

I'm wondering if this problem can be approached as a standard convolution problem.

[pavanky]

Especially if you are doing it in frequency space, all you would need to do is 1 forward FFT and n reverse FFTs.

Alternatively you can just perform a prefix sum operation and subtract each (n - k)th element from nth element for results in the kth iteration. This could be even faster.