Quantas magnitudes de Fourier eu tenho que calcular antes que uma FFT se torne mais eficiente que uma DFT?

8

Eu preciso calcular apenas um pequeno número de componentes de Fourier de baixa frequência de uma matriz bidimensional complexa. Estarei computando os mesmos componentes de Fourier repetidamente conforme a matriz de entrada muda. Claramente, no limite em que eu quero apenas um componente de Fourier, seria mais rápido construir uma matriz DFT que fornece o componente que eu estou procurando e multiplicar por essa matriz repetidamente.

No outro limite, se eu quisesse todos os componentes de Fourier, seria mais rápido usar uma FFT.

Em que momento fica mais rápido calcular a FFT da matriz e simplesmente retirar os componentes que estou procurando?

Se isso faz diferença, na minha situação particular, a matriz de entrada será algo como . Estou usando o MATLAB, o que significa que minha FFT é feita usando FFTW, e uma multiplicação de matrizes para uma DFT de matriz é feita por qualquer algoritmo de multiplicação de matrizes que o MATLAB usa sob o capô.256×256

Colin K
fonte
2
Primeiro, apenas uma observação: o DFT é a transformação matemática e o FFT é um algoritmo rápido para computá-los; por DFT, parece-me que você quer dizer a implementação direta da expressão discreta da transformação de Fourier. Segundo: você não precisa do inverso? Nesse caso, você só pode implementar a transformação para os elementos necessários.
Fcruz 02/04/12
Sim, estou ciente da distinção entre a DFT e a FFT. Talvez a maneira como usei os termos não seja comum além de mim e de meus colegas. O que você disse é essencialmente correto: uso o termo "DFT" para me referir a algum cálculo direto de um ou mais coeficientes de Fourier. A FFT, embora eficiente, é restrita à computação de frequências de DC a duas vezes a frequência de Nyquist, com um espaçamento de amostra de 1 / N, em que N é o tamanho da matriz. Um DFT em geral é capaz de calcular um subconjunto dessas frequências, ou mesmo intermediárias (k / N para k não inteiro), mas não é tão eficiente.
Colin K
@ fcruz: Além disso, "implementar a transformação apenas para os elementos que eu preciso" é exatamente o que essa pergunta trata. Estou perguntando quantos elementos posso calcular por uma DFT antes que simplesmente seja mais rápido fazer a FFT inteira e depois jogar fora os valores que não preciso. A resposta que rcompton deu parece estar bastante correta nesse ponto.
Colin K

Respostas:

9

17

Muito e muito trabalho foi implementado em boas implementações de fft e é improvável que você seja capaz de superar com êxito uma boa biblioteca de fft. Por exemplo, o fftw "se adapta automaticamente à sua máquina, ao seu cache, ao tamanho da sua memória, ao número de registros e a todos os outros fatores que normalmente tornam impossível otimizar um programa para mais de uma máquina" ref nesta página .

Você está certo de que há situações em que é mais rápido calcular apenas alguns produtos pontuais, mas isso depende muito do sistema.

Um 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.

Portanto, quando há 4096 pontos de dados computando o fft inteiro, leva apenas ~ 17x mais tempo do que o cálculo de um único produto pontual.

dranxo
fonte
1
Qual é o inicial "17." no seu post?
Shuhalo
2
Essa é a resposta :) Fiz um teste em minha própria máquina e o resultado obtido concorda com isso, mais ou menos, até que o tamanho da matriz de entrada chegue a 64 ou menos. A resposta como um todo, embora não seja muito clara, é por isso que ainda não a aceitei (por exemplo, não deveria haver necessidade de produzir dftmtx (256 ^ 2)!), Mas em breve ninguém mais entra na conversa.
Colin K
4

Como alternativa, você pode usar o algoritmo de Goertzel para calcular diretamente os componentes de frequência nos quais está interessado.

eglaser
fonte
+1. Definitivamente uma boa sugestão. No entanto, para minha grande surpresa, o algoritmo goertzel incluído no Matlabs Signal Processing Toolkit é lamentavelmente lento. É pior que o DFT e o FFT para qualquer combinação de tamanho da matriz de entrada e número de valores de saída que eu possa testar.
Colin K
1
Eu suspeito que, embora o próprio algoritmo possa ser computacionalmente mais eficiente em alguns casos, a implementação do Matlab é escrita em puro Matlab, enquanto a FFT e a matriz multiplicada usada na DFT são escritas em C. altamente otimizado.
Colin K
No caso da Goertzel alg., Uma discussão sobre sua eficiência algorítmica comparada à FFT foi abordada nesta parte da aula do curso discreto de sinal de tempo no MIT.
Fcruz 5/04
A implementação ingênua do algoritmo de Goertzel pode gerar resultados imprecisos, portanto, alguns cuidados são necessários. Pode-se considerar o uso da modificação proposta por Christian Reinsch. Veja, por exemplo, a discussão em Bulirsch / Stoer .
JM