KJlaccHoeUM9l commented on PR #13999: URL: https://github.com/apache/tvm/pull/13999#issuecomment-1447754438
Hello @masahi! Thanks for the review! First of all, my task was to support the DFT operator for ONNX front-end. During the execution of this task, I was based on the [ONNX documentation](https://github.com/onnx/onnx/blob/main/docs/Operators.md#DFT) and [general information](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) about DFT. All functionality described in the documentation has been supported in this PR. It is also worth noting that the ONNX documentation does not mention that the implementation uses the Fast Fourier Transform. However, if you look at the [source code](https://github.com/onnx/onnx/blob/72300aab201f81615885f13f0f4cb6f331320be0/onnx/reference/ops/op_dft.py#L19) of ONNX, you can see that "under hood" ONNX uses [numpy.fft](https://numpy.org/doc/stable/reference/generated/numpy.fft.fft.html#numpy.fft.fft), which implements one-dimensional n-point fast Fourier transform ([FFT](https://en.wikipedia.org/wiki/Fast_Fourier_transform)) with a computational complexity of `O(NlogN)` (where N is the length of the Fourier transform). The implementation refers to [Cooley-Tukey FFT algorithm](https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm). > I wonder how exactly you are going to do it. It would be a significant effort if we need to support all input size (e.g. not just a power of two) In general, the Cooley-Tukey algorithm re-expresses DFT of an arbitrary composite size `N=N1*N2`. But the best computational efficiency is achieved when N is a power of two. As a first approximation, I wanted to implement two algorithms (direct and fast) and, depending on `N`, use the appropriate algorithm. > both real / complex transform, inverse transform etc All these transformations are supported right now and do not affect the future addition of FFT. One of the possible improvements could be a separate implementation of the algorithm for the real input, because in this case, we need to do only half of the calculations (the imaginary part of the input is identically equal to zero) > support both CPU and GPU. Right now, the default TOPI operators for the CPU and GPU are implemented. For FFT it will look similar. > Not to mention the performance problem compared to MKL / cuFFT. Yes, that's a good point, but it's outside the scope of this PR. This PR supports DFT operator. Performance issues can be taken out for future research. In conclusion, I also want to add that the project in which this PR was created unexpectedly ended. Therefore, the addition of the FFT will be delayed for some time. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
