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ô.
fonte
Respostas:
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:
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.
fonte
Como alternativa, você pode usar o algoritmo de Goertzel para calcular diretamente os componentes de frequência nos quais está interessado.
fonte