Problem 42793. Fast 1-D Convolution (full shape)

This is the first problem in the fast 1-D convolution series. This problem asks you to find a fast algorithm to compute the 1-D convolution in its full output shape.

There exists a fast 1-D convolution algorithm way more efficient than MATLAB's built-in conv function invoked in the form conv(u,v,'full'), and the performance improvement is more pronounced when length(u) and/or length(v) are large. Do you know how? Try it out.

• Next problem: Fast 1-D Convolution (same shape).