Paper Info
Title
An exact, cache-localized algorithm for the sub-quadratic convolution of hypercubes.
Abstract
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 is large, these algorithms become more challenging. A method is proposed for performing exact hypercube convolution in sub-quadratic time. The method outperforms FFTPACK, called via numpy, and FFTW, called via pyfftw) for hypercube convolution. Embeddings in hypercubes can be paired with sub-quadratic hypercube convolution method to construct sub-quadratic algorithms for variants of vector convolution.
Year
Venue
Field
2016
arXiv: Computational Geometry
Discrete mathematics,Combinatorics,Convolution,Convolution theorem,Curse of dimensionality,Fourier transform,Time complexity,Kernel (image processing),Overlap–add method,Hypercube,Mathematics
DocType
Volume
Citations 
Journal
abs/1608.00206
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Oliver Serang101.01