Надежный и быстрый FFT в [закрытом] Java

FFTW - это «самое быстрое преобразование Фурье на западе», и в нем есть несколько оболочек Java:

http://www.fftw.org/download.html

Надеюсь, что это поможет!