Hola.Hace un tiempo yo tambien tuve que trabajar con transformadas de Fourier. En dos dimensiones, para imágenes. Las librerías que empleé las puedes encontrar en http://www.fftw.org/.
Estas librerías están avaladas por el MIT, y a mi me funcionaron bastante bien, tras hacer unas ligeras modificaciones para adaptarlas a mis necesidades. Están bien documentadas (ingles). Es la transformada discreta, que es la que necesitas para el tipo de datos que tienes.
Échala un vistazo, y si necesitas mas ayuda, pídela.
Saludos.