Provide Fast Fourier Transform (FFT)

[mrfh92]

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 the fft-module in PyTorch:

• fftn/ifftn: FFT/iFFT of an $n$-dim array along up to $n$ axes
• fft/ifft: FFT/iFFT of an $n$-dim array along a single axis only
• fft2/ifft2: FFT/iFFT of an $n$-dim array along two axes only
• the same with r...: modifications in the case of real-valued input arrays
• the same with h...: modifications in the case of hermitian input arrays
• if time permits: the "helper functions"

Can potentially be used for convolutions (#1248 )

Material

• arXiv:1804.09536 may serve as an overview on $n$-dimensional FFT. Heat's data distribution is referred to as "slab decomposition", so actually we will do something much more easy than described in this paper.
• There is a fft-module in PyTorch that we can use for process-local computations.

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:

1. do locally on each process: FFT along all axes $i$ such that $i \in dim$ and $i\neq split$ (use the respective PyTorch function). If $split \notin dim$ we are done.
2. If $split \in dim$ now resplit the array to a different split axis.
3. do locally on each process: FFT (1-dimensional, PyTorch) along axis $split$ (the original split axis, of course, which is currently no more the split axis...)
4. resplit back to obtain same split-axis as at the beginning

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.

[mrfh92]

@Sai-Suraj-27 for whatever reason github lets me only assign your old account ... can you try to assign your new account yourself?

[Sai-Suraj-27]

@mrfh92 sir, assign it to me...👍

[github-actions]

Branch features/1097-Provide_Fast_Fourier_Transform_FFT created!

[ClaudiaComito]

I've taken over this issue and started implementation in the branch above