Questions tagged [fft]

The tag has no usage guidance.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
124 views

What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
2
votes
0answers
84 views

Is gaussian smoothing possible in less operations than O(N log N)

Gaussian filtering is popular in applications, for my question it can be written as (I've fixed the size of window): $$y_i = \sum_{j = 1}^{n} x_j e^{(i - j)^2}, \qquad i = 1, 2, ..., n $$ One can ...
1
vote
0answers
32 views

Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?

In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime. I've been toying with an idea for a ...