fft(3F)
FFT, libfft - libcomplib.sgimath - Fast Fourier Transforms
As shipped in IRIX 6.5.15. Unchanged since IRIX 6.5.
NAME FFT, libfft - libcomplib.sgimath - Fast Fourier Transforms DESCRIPTION A set of Fast Fourier Transform (FFT) modules, fully optimized for SGI computers. On parallel systems, Multi Dimensional FFTs, as well as large 1D transforms are computed in parallel. The FFT modules are provided with both a C and a Fortran interface. They are part of the complib.sgimath library. These modules include: - One, multiple one, two and three dimensional FFTs, real to complex, complex to real and complex to complex, in single and double precision. - Scaling routines. - Fourier Product routines. C interface For the C interface two types "complex" and "zomplex" have been defined as structures of two floating point variables ( re, im ). They are equivalent to the "complex" and "double complex" Fortran types. typedef struct { float re; float im; } complex; typedef struct { double re; double im; } zomplex; These types as well as the prototypes of the different functions for FFTs are defined in the "/usr/include/fft.h" header file. In C, Multi Dimensional sequences are actually stored into a 1D array (contiguous data). For example, an MxN 2D sequence must be stored into an array of size LxN (M <= L), and the sample at index (i,j) is actually stored as element Array[i+L*j] - NAMING CONVENTIONS Initialization - cfft_di, zfft_di, sfft_dui, dfft_dui: initialize the twiddle factors needed for the FFT computation, e.g. cfft1di. Computation - cfft_d, zfft_d : compute the Direct Fourier Transform or the Inverse Fourier Transform complex data, e.g. zfft2d. scfft_du, dzfft_du : Direct Fourier Transform of a real array input. Although the transform is performed in place, the output is to be considered as an array of complex data, e.g. scfftm1du. csfft_du, zdfft_du : Inverse Fourier Transform for a real value sequence. Although the transform is performed in place, the input is taken as a Complex value sequence, while the ouput is a real sequence. (e.g. zdfft1du). Fourier Product - cprod_d, zprod_d, sprod_du, dprod_du: in place product of the Fourier Transform of a sequence with the Fourier Transform of a filter, e.g. cprod3d . (The product of the two Fourier Transforms is equal to the tranform of the convolution of the two corresponding sequences.) Scaling - sscal_du, dscal_du, cscal_d, zscal_d : Scales the sequence by a real value, e.g. dscal2du . This may be usefull as the FFTs are not normalized and after a double call( direct-transform, inverse-transform) the final output is equal to the input scaled by the number of samples. SUMMARY NOTE: The Development Magic (-o32) FFT library differs from the -n32/-64 FFT library. The -o32 FFT library contains only a subset of the routines in the -n32/-64 library. See the o32fft man page for details. Functions and Routines: ----------------------------------------------------------------------- | | | Multiple | | | | | 1 Dimension | 1 Dimension | 2 Dimensions | 3 Dimensions | | | | | | | ----------------------------------------------------------------------- | REAL | scfft1dui | scfftm1dui | scfft2dui | scfft3dui | | to | scfft1du | scfftm1du | scfft2du | scfft3du | | COMPLEX | csfft1du | csfftm1du | csfft2du | csfft3du | | | sprod1du | sprodm1du | sprod2du | sprod3du | | Single | sscal1d | sscalm1d | sscal2d | sscal3d | | Precision | | | | | ----------------------------------------------------------------------- | REAL | dzfft1dui | dzfftm1dui | dzfft2dui | dzfft3dui | | to | dzfft1du | dzfftm1du | dzfft2du | dzfft3du | | COMPLEX | zdfft1du | zdfftm1du | zdfft2du | zdfft3du | | | dprod1du | dprodm1du | dprod2du | dprod3du | | Double | dscal1d | dscalm1d | dscal2d | dscal3d | | Precision | | | | | ----------------------------------------------------------------------- | COMPLEX | | | | | | to | cfft1di | cfftm1di | cfft2di | cfft3di | | COMPLEX | cfft1d | cfftm1d | cfft2d | cfft3d | | | cprod1d | cprodm1d | cprod2d | cprod3d | | Single | cscal1d | cscalm1d | cscal2d | cscal3d | | Precision | | | | | ----------------------------------------------------------------------- | COMPLEX | | | | | | to | zfft1di | zfftm1di | zfft2di | zfft3di | | COMPLEX | zfft1d | zfftm1d | zfft2d | zfft3d | | | zprod1d | zprodm1d | zprod2d | zprod3d | | Double | zscal1d | zscalm1d | zscal2d | zscal3d | | Precision | | | | | ----------------------------------------------------------------------- LINKING with complib.sgimath C programs: for serial binaries cc -o my_exe my_source.c -lcomplib.sgimath for parallel executables cc -o my_parallel_exe my_source.c -lcomplib.sgimath_mp -mp Fortran programs: for serial binaries f77 -o my_exe my_source.f -lcomplib.sgimath for parallel executables f77 -o my_parallel_exe my_source.f -lcomplib.sgimath_mp -mp PERFORMANCE To be Fast the Fast Fourier Transform relies on the factorization of the array size into small prime factors. The smaller the factors, the lesser the floating point operations required. E.g. a 1D Fourier transform of size 899(29*31) is much more expensive to compute than one of size 900(2*2*3*3*5*5), (roughly ten times more floating point operations). To boost performance special code exists for Radices 2, 3, 4 and 5. Note, the radix 4 is equivallent to a double radix 2 implementation, but it reduces computation cost by 15%. For Multiple 1D, or 2D or 3D FFTs, although the same computation could be performed using 1D FFTs in a loop, the corresponding modules are more efficient as they involve less overhead, and as the individual 1D FFTs can be pipelined together. Furthermore, the Multiple 1D, or 2D or 3D modules are parallel, thus enabling another performance level increase without any work in the user source. SEE ALSO o32fft cfft1d, cfftm1d, cfft2d, cfft3d, cfft1di, cfftm1di, cfft2di, cfft3di, zfft1d, zfftm1d, zfft2d, zfft3d, zfft1di, zfftm1di, zfft2di, zfft3di, scfft1du, csfft1du, scfft1dui, dzfft1du, zdfft1du, dzfft1dui, scfftm1du, csfftm1du, scfftm1dui, dzfftm1du, zdfftm1du, dzfftm1dui, scfft2du, csfft2du, scfft2dui, dzfft2du, zdfft2du, dzfft2dui, scfft3du, csfft3du, scfft3dui, dzfft3du, zdfft3du, dzfft3dui, cprod1d, zprod1d, sprod1du, dprod1du, cprodm1d, zprodm1d, sprodm1du, dprodm1du, cprod2d, zprod2d, sprod2du, dprod2du, cprod3d, zprod3d, sprod3du, dprod3du, cscal1d, zscal1d, sscal1d, dscal1d, cscalm1d, zscalm1d, sscalm1d, dscalm1d, cscal2d, zscal2d, sscal2d, dscal2d, cscal3d, zscal3d, sscal3d, dscal3d