You know, I'll go out on the limb and say (unhelpfully) that a FFT is more efficient than any general dense matvec.

Bah, when you've maxxed out your cuda cores, who's to prevent you from reaching for those sweet tensor core 100+ tflops mat-mul now?

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

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.

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.

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

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.

Vandermonde. He was not Dutch, he was French. https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermond...

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

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

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