FFT(3F) FFT(3F)
FFT, libfft - libcomplib.sgimath - Fast Fourier Transforms
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.
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] -
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
Page 1
FFT(3F) FFT(3F)
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.
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 | | | | |
Page 2
FFT(3F) FFT(3F)
| 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
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.
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,
Page 3
FFT(3F) FFT(3F)
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
FFT(3F) FFT(3F)
FFT, libfft - libcomplib.sgimath - Fast Fourier Transforms
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.
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] -
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
Page 1
FFT(3F) FFT(3F)
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.
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 | | | | |
Page 2
FFT(3F) FFT(3F)
| 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
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.
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,
Page 3
FFT(3F) FFT(3F)
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
PPPPaaaaggggeeee 4444 [ Back ]
|
