3 ms·

This is analogous to saying "an umbrella is better than a toaster". They are two different things.

ok123456 5y ago
You can implement a DFT with matrix multiplication using the vandermonde matrix with roots of the unitary polynomial as the basis.
amelius 5y ago
Not if you perform these operations in order to obtain a Fourier transform.
cdavid 5y ago
Fourier transform, more exactly DFT, is a special case of matrix multiplication, when seen as a linear operator. The fact that you can do operations faster than the usual N*2 matrix / vector operation is due to the specific form of the underlying matrix (Van Der Mont matrix). So they are not that different: the specific structure of the Fourier basis allows for more efficient matrix * vector operation.
- deleted 5y ago
  [deleted]
- layoutIfNeeded 5y ago
  Vandermonde. He was not Dutch, he was French. https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermonde https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermond...
Joker_vD 5y ago
Why do people insist on comparing only things that are same? The same things are same, no point whatsoever comparing them: they're same! No, you should only compare things that are different, that way you learn more about their differences. And what's better, an umbrella or a toaster, depends on the one's goals: if one'd like to fry some bread, toaster is more useful; if one'd like to cover from rain, umbrella is far superior, although toaster could used be too; if one'd like to drive a nail into the wall, toaster again is better; etc.
- 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 ago
    The 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
hamiltonkibbe 5y ago
They are different things, but you can use both to protect you from the rain, and an umbrella does that more efficiently than a toaster. The drawback is that the umbrella doesn't generalize to the broader field of bagel toasting

You can implement a DFT with matrix multiplication using the vandermonde matrix with roots of the unitary polynomial as the basis.

amelius 5y ago

Not if you perform these operations in order to obtain a Fourier transform.

cdavid 5y ago

Fourier transform, more exactly DFT, is a special case of matrix multiplication, when seen as a linear operator. The fact that you can do operations faster than the usual N*2 matrix / vector operation is due to the specific form of the underlying matrix (Van Der Mont matrix). So they are not that different: the specific structure of the Fourier basis allows for more efficient matrix * vector operation.

deleted 5y ago
[deleted]
layoutIfNeeded 5y ago
Vandermonde. He was not Dutch, he was French. https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermonde https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermond...

Joker_vD 5y ago

Why do people insist on comparing only things that are same? The same things are same, no point whatsoever comparing them: they're same! No, you should only compare things that are different, that way you learn more about their differences. And what's better, an umbrella or a toaster, depends on the one's goals: if one'd like to fry some bread, toaster is more useful; if one'd like to cover from rain, umbrella is far superior, although toaster could used be too; if one'd like to drive a nail into the wall, toaster again is better; etc.

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 ago
  The 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

hamiltonkibbe 5y ago

They are different things, but you can use both to protect you from the rain, and an umbrella does that more efficiently than a toaster. The drawback is that the umbrella doesn't generalize to the broader field of bagel toasting