My favorite application of the Fourier transform is converting convolution into pointwise multiplication. This is used to speed up multiple sequence alignment in bioinformatics.