¿Cuántas magnitudes de Fourier debo calcular antes de que una FFT sea más eficiente que una DFT?

8

Necesito calcular solo un pequeño número de componentes de Fourier de baja frecuencia de una matriz compleja de 2 dimensiones. Calcularé los mismos componentes de Fourier una y otra vez a medida que cambie la matriz de entrada. Claramente, en el límite donde solo quiero un componente de Fourier, sería más rápido construir una matriz DFT que proporcione el componente que busco, y multiplicar por esa matriz repetidamente.

En el otro límite, si quisiera todos los componentes de Fourier, sería más rápido usar un FFT.

¿En qué punto se vuelve más rápido calcular la FFT de la matriz y simplemente extraer los componentes que busco?

Si hace la diferencia, en mi situación particular, la matriz de entrada será algo así como . Estoy usando MATLAB, por lo que eso significa que mi FFT se hace usando FFTW, y una multiplicación de matriz para una DFT de matriz se realiza a través del algoritmo de multiplicación de matriz que MATLAB usa debajo del capó.256×256

Colin K
fuente
2
Primero, solo una nota: DFT es la transformación matemática y FFT es un algoritmo rápido para calcularlos, por DFT me parece que te refieres a la implementación directa de la expresión de transformación discreta de Fourier. Segundo: ¿No necesitas lo inverso? si es así, solo podría implementar la transformación para los elementos que necesita.
fcruz
Sí, soy consciente de la distinción entre el DFT y el FFT. Quizás la forma en que he usado los términos no es común más allá de mí y mis colegas. Lo que usted dijo es esencialmente correcto: uso el término "DFT" para referirme a un cálculo directo de uno o más coeficientes de Fourier. La FFT, aunque eficiente, está restringida a frecuencias de computación de CC a dos veces la frecuencia de Nyquist, con un espaciado de muestra de 1 / N donde N es el tamaño de la matriz. Un DFT en general es capaz de calcular un subconjunto de estas, o incluso frecuencias intermedias (k / N para k no entero), pero no es tan eficiente.
Colin K
@fcruz: Además, "implementar la transformación solo para los elementos que necesito" es exactamente de lo que trata esta pregunta. Estoy preguntando cuántos elementos puedo calcular por un DFT antes de que simplemente sea más rápido hacer todo el FFT y luego tirar los valores que no necesito. La respuesta que dio rcompton parece ser bastante correcta en este punto.
Colin K

Respuestas:

9

17)

Mucho y mucho trabajo se ha invertido en buenas implementaciones fft y es poco probable que pueda superar de manera confiable una buena biblioteca fft. Por ejemplo, fftw "se adapta automáticamente a su máquina, su caché, el tamaño de su memoria, el número de registros y todos los demás factores que normalmente hacen imposible optimizar un programa para más de una máquina" ref esta página .

Tiene razón en que hay situaciones en las que es más rápido calcular algunos productos de puntos, pero dependerá mucho del sistema.

Un experimento:

EDU>> n = 256^2;
EDU>> x = randn(n,1);
EDU>> d = randn(1,n); %really, you should take a row from the output of the dftmtx command. But dftmtx(n) won't fit on my laptop...
EDU>> tic;d*x;toc; %time to compute a single frequency from the dft matrix
Elapsed time is 0.000225 seconds.
EDU>> tic;fft(x);toc; %time to compute the entire fft
Elapsed time is 0.003909 seconds.

Entonces, cuando hay 4096 puntos de datos que calculan todo el fft, solo tarda ~ 17 veces más que calcular un solo producto de punto.

dranxo
fuente
1
¿Cuál es el "17." inicial en tu post?
shuhalo
2
Esa es la respuesta :) Realicé una prueba en mi propia máquina y el resultado que obtuve está de acuerdo con esto, más o menos, hasta que el tamaño de la matriz de entrada llega a 64 o menos. Sin embargo, la respuesta en su conjunto no es muy clara, por lo que aún no la he aceptado (¡por ejemplo, realmente no debería ser necesario producir dftmtx (256 ^ 2)!), Pero pronto lo haré si nadie más interviene.
Colin K
4

Como alternativa, podría considerar el uso del algoritmo de Goertzel para calcular directamente los componentes de frecuencia que le interesan.

eglaser
fuente
+1. Definitivamente una buena sugerencia. Sin embargo, para mi gran sorpresa, el algoritmo de goertzel incluido en Matlabs Signal Processing Toolkit es lamentablemente lento. Es peor que el DFT y el FFT para cualquier combinación de tamaño de matriz de entrada y número de valores de salida que pueda probar.
Colin K
1
Sospecho que mientras que el algoritmo en sí mismo puede ser computacionalmente más eficiente en algunos casos, la aplicación Matlab está escrito en puro Matlab, mientras que la FFT y la matriz utilizada se multipliquen en la DFT son ambos escritos en C. altamente optimizado
Colin K
En el caso de Goertzel alg., Una discusión sobre su eficiencia algorítmica en comparación con la FFT había sido cubierta en esta parte del curso de señalización discreta en el MIT.
fcruz
La implementación ingenua del algoritmo de Goertzel puede dar lugar a resultados inexactos, por lo que es necesario tener cuidado. Uno podría considerar usar en su lugar la modificación propuesta por Christian Reinsch. Ver, por ejemplo, la discusión en Bulirsch / Stoer .
JM