An exact, cache-localized algorithm for the sub-quadratic convolution of hypercubes

Oliver Serang

Fast multidimensional convolution can be performed naively in quadratic time and can often be performed more efficiently via the Fourier transform; however, when the dimensionality…