3 ms·
My statement was as approximate as the one I was replying to. If the original statement had been "you can use FFT to implement some operations involving matrix
by mochomocha 5y ago
My statement was as approximate as the one I was replying to. If the original statement had been "you can use FFT to implement some operations involving matrix multiplication faster" I wouldn't have taken issue with it. But saying "FFT is faster than matrix multiplication" has little meaning.
- vladTheInhaler 5y agoThe naive implementation of the DFT in terms of a matrix-vector multiplication has time complexity O(n^2) [1]. The point is that the FFT approach is much faster than that implementation. [1] https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix