Closed mrfh92 closed 10 months ago
@Sai-Suraj-27 for whatever reason github lets me only assign your old account ... can you try to assign your new account yourself?
@mrfh92 sir, assign it to me...👍
Branch features/1097-Provide_Fast_Fourier_Transform_FFT created!
I've taken over this issue and started implementation in the branch above
Feature functionality Provide routines for Fast Fourier Transform (FFT) and its inverse for $n$-dimensional
DNDarray
's. Fourier transform along a single axis, a prescribed subset of axes, or along all axes should be possible. This would correspond roughly to the functionality of thefft
-module in PyTorch:fftn
/ifftn
: FFT/iFFT of an $n$-dim array along up to $n$ axesfft
/ifft
: FFT/iFFT of an $n$-dim array along a single axis onlyfft2
/ifft2
: FFT/iFFT of an $n$-dim array along two axes onlyr...
: modifications in the case of real-valued input arraysh...
: modifications in the case of hermitian input arraysCan potentially be used for convolutions (#1248 )
Material
Suggestions and Hints The discrete Fourier transform $\mathcal{F}$ of an $n$-dimensional array is given by $\mathcal{F}=\mathcal{F}{0}\circ... \circ\mathcal{F}{d-1}$ where $\mathcal{F}_i$ denotes the 1-dimensional (i.e. usual) DFT along the $i$-th axis. Consequently, a similar factorization holds true for the inverse DFT as well.
The "only" tricky part when adding parallelization to this concept is the Fourier transformation along the split-axis. I would like to recommend something like the following approach:
Similarly, also the inverse FFT (iFFT) can be implemented. Of course, this is just a very first idea, how FFT and iFFT could be implemented in Heat; if you have a good idea for a more elaborate, more efficient implementation, feel free to tell me :) Since PyTorch-FFT already supports CPU and GPU, the corresponding implementation in Heat should work on CPU und GPU without particular additional effort.