# Implicitly padded FFT convolution - ID: 2297 - Canonical URL: https://synthcore.org/idea/2297/implicitly-padded-fft-convolution - API JSON: https://synthcore.org/api/idea/2297.json - API Markdown: https://synthcore.org/api/idea/2297.md - Verification status: failed_benchmark - Source: [arXiv:2608.14497](https://arxiv.org/abs/2608.14497) - Category: memory - Solves: speedup, memory - ML areas: cnn, ssm, inference-speedup, memory - Math tags: harmonic-analysis, linear-algebra, numerical-analysis - Ratings: usefulness 7/10; difficulty 7/10; novelty 6/10 ## Idea description Replace explicit zero-padding before FFT convolution by the paper's mixed-radix decomposition, which injects zeros through bounded tile sums and never allocates the padded input. The resulting transform is mathematically identical to the length-M transform of the explicitly padded signal, while reducing temporary storage and potentially memory bandwidth. ## Mathematical statement Let f={f_j}_{j=0}^{L-1} be an input of length L, let M>=L be the desired transform length, choose m in N, and define p=ceil(L/m) and q=ceil(M/m). Reindex input indices as j=tm+s with t=0,...,p-1 and s=0,...,m-1, and frequency indices as k=q ell+r with ell=0,...,m-1 and r=0,...,q-1. With zeta_N=exp(2 pi i/N), the paper's implicit zero-padded transform is F_{q ell+r}=sum_s zeta_m^{ell s} zeta_{qm}^{rs} sum_t zeta_q^{rt} f_{tm+s}, where f_{tm+s}=0 whenever tm+s>=L. Thus the zero padding is represented by a predicate inside the tile sum rather than by a materialized array. The inverse is f_{tm+s}=(1/(qm)) sum_r zeta_q^{-tr} zeta_{qm}^{-sr} sum_ell zeta_m^{-s ell}F_{q ell+r}. For convolution of f and g, choose M>=L+K-1, compute both implicit transforms, multiply spectra pointwise, and inverse-transform. ## Key formulas - $$j=tm+s,\quad t=0,\ldots,p-1,\quad s=0,\ldots,m-1,\qquad k=q\ell+r,\quad \ell=0,\ldots,m-1,\quad r=0,\ldots,q-1.$$ - $$F_{q\ell+r}=\sum_{s=0}^{m-1}\zeta_m^{\ell s}\zeta_{qm}^{rs}\sum_{t=0}^{p-1}\zeta_q^{rt}f_{tm+s},\qquad \zeta_N=e^{2\pi i/N}.$$ - $$f_{tm+s}=\frac{1}{qm}\sum_{r=0}^{q-1}\zeta_q^{-tr}\zeta_{qm}^{-sr}\sum_{\ell=0}^{m-1}\zeta_m^{-s\ell}F_{q\ell+r}.$$ - $$Y=\operatorname{IFFT}_M\!\left(\operatorname{FFT}_M(f_{\mathrm{implicit\ pad}})\odot\operatorname{FFT}_M(g_{\mathrm{implicit\ pad}})\right),\qquad M\ge L+K-1.$$ ## Implementation notes Integrate this in the FFT convolution path of a long 1D CNN, temporal SSM, or neural-operator layer, specifically where the framework currently executes pad(x, (0,M-L)) followed by FFT. Given input length L and kernel length K, choose M as a convenient FFT length satisfying M>=L+K-1, and choose a tile size m that is friendly to the target CPU or GPU. Store only the original tensor x[B,C,L]. For each tile coordinate (t,s), load x[...,tm+s] if tm+s