 In many applications, the input data for the DFT are purely real, in which case the outputs satisfy the symmetry

and efficient FFT algorithms have been designed for this situation (see e.g.Sorensen, 1987).One approach consists of taking an ordinary algorithm (e.g.