FFT_SERIAL\ Fast Fourier Transform {#fft_serial-fast-fourier-transform align=”center”} ======================
FFT_SERIAL is a C++ program which demonstrates the computation of a Fast Fourier Transform, and is intended as a starting point for developing a parallel version using OpenMP.
On an Apple PowerPC G5 with two processors, the following results were observed:
N Time MegaFLOPS ——— ————- ———– 2 4.3525e-07 22.9753 4 1.15245e-06 34.7087 8 2.20385e-06 54.4502 16 4.509e-06 70.9692 32 6.798e-06 117.682 64 1.61065e-05 119.207 128 3.28125e-05 136.533 256 7.6573e-05 133.729 512 0.000157155 146.607 1024 0.00035841 142.853 2048 0.00075819 148.564 4096 0.00170309 144.302 8192 0.00348095 152.970 16384 0.00811195 141.382 32768 0.0173951 141.281 65536 0.0402766 130.172 131072 0.083454 133.500 262144 0.184454 127.907 524288 0.382927 130.070 1048576 0.835447 125.511
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
FFT_SERIAL is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.
FFT_OPENMP, a C++ program which computes a Fast Fourier Transform using OpenMP.
FIRE_SERIAL, a C++ program which simulates a forest fire over a rectangular array of trees, starting at a single random location. It is intended as a starting point for the development of a parallel version.
HEATED_PLATE, a C++ program which solves the steady state heat equation in a 2D rectangular region, and is intended as a starting point for implementing an OpenMP parallel version.
MD, a C++ program which carries out a molecular dynamics simulation, and is intended as a starting point for developing a parallel version using OpenMP.
MXM_SERIAL, a C++ program which sets up a matrix multiplication problem A=B*C, intended as a starting point for implementing a parallel version.
OPENMP, C++ programs which illustrate the use of the OpenMP application program interface for carrying out parallel computations in a shared memory environment.
POISSON_SERIAL, a C++ program which computes an approximate solution to the Poisson equation in a rectangle, and is intended as the starting point for the creation of a parallel version.
PRIME_SERIAL, a C++ program which counts the number of primes between 1 and N, intended as a starting point for the creation of a parallel version.
QUAD_SERIAL, a C++ program which approximates an integral using a quadrature rule, and is intended as a starting point for parallelization exercises.
SEARCH_SERIAL, a C++ program which searches the integers from A to B for a value J such that F(J) = C. this version of the program is intended as a starting point for a parallel approach.
SFTPACK, a C++ library which implements the “slow” Fourier transform, intended as a teaching tool and comparison with the fast Fourier transform.
SINE_TRANSFORM, a C++ library which demonstrates some simple properties of the discrete sine transform.
SUBSET_SUM_SERIAL, a C++ program which seeks solutions of the subset sum problem, in which it is desired to find a subset of a set of integers which has a given sum; this version of the program is intended as a starting point for a parallel approach.
You can go up one level to the C++ source codes.
Last revised on 23 March 2009.