FFT_SERIAL
Fast Fourier Transform

FFT_SERIAL is a MATLAB program which demonstrates the computation of a Fast Fourier Transform.

This implementation of the Fast Fourier Transform does not run efficiently with MATLAB. However, we can still compute some interesting statistics about the time, the computational rate, and so on.

On an Apple PowerPC G5 with two processors, the following results were observed:

N Iterations Time Time/Call MegaFLOPS

2 10,000 1.132 5.6e-05 0.176

4 10,000 2.264 1.1e-04 0.353

8 10,000 3.458 1.7e-04 0.693

16 10,000 6.064 3.0e-04 1.055

32 1,000 1.066 5.3e-04 1.499

64 1,000 2.326 1.1e-03 1.650

128 1,000 5.122 2.5e-03 1.749

256 1,000 11.959 5.9e-03 1.712

512 100 2.932 1.4e-02 1.571

1024 100 19.697 9.8e-02 0.519

N	Iterations	Time	Time/Call	MegaFLOPS
2	10,000	1.132	5.6e-05	0.176
4	10,000	2.264	1.1e-04	0.353
8	10,000	3.458	1.7e-04	0.693
16	10,000	6.064	3.0e-04	1.055
32	1,000	1.066	5.3e-04	1.499
64	1,000	2.326	1.1e-03	1.650
128	1,000	5.122	2.5e-03	1.749
256	1,000	11.959	5.9e-03	1.712
512	100	2.932	1.4e-02	1.571
1024	100	19.697	9.8e-02	0.519

Languages:

FFT_SERIAL is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

HEATED_PLATE, a MATLAB program which solves the steady (time independent) heat equation in a 2D rectangular region, and is intended as a starting point for implementing a parallel version.

LINPACK_BENCH, a MATLAB program which measures the time taken by LINPACK to solve a particular linear system.

LINPACK_BENCH_BACKSLASH, a MATLAB program which measures the time taken by LINPACK to solve a particular linear system, and uses MATLAB's builtin "backslash" operator to do the solving.

MATLAB_PARALLEL, MATLAB programs which illustrate "local" parallel programming on a single computer with MATLAB's Parallel Computing Toolbox.

MD, a MATLAB program which carries out a molecular dynamics simulation, and is intended as a starting point for developing a parallel version using OpenMP.

POISSON_SERIAL, a MATLAB 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.

POWER_METHOD, a MATLAB library which carries out the power method for finding a dominant eigenvalue and its eigenvector.

PRIME_SERIAL, a MATLAB 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 MATLAB program which approximates an integral using a quadrature rule, and is intended as a starting point for parallelization exercises.

SATISFY, a MATLAB program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem.

TIMER, MATLAB programs which demonstrate how to compute CPU time or elapsed time.

Reference:

Wesley Petersen, Peter Arbenz,
Introduction to Parallel Computing - A practical guide with examples in C,
Oxford University Press,
ISBN: 0-19-851576-6,
LC: QA76.58.P47.
Rohit Chandra, Leonardo Dagum, Dave Kohr, Dror Maydan, Jeff McDonald, Ramesh Menon,
Parallel Programming in OpenMP,
Morgan Kaufmann, 2001,
ISBN: 1-55860-671-8,
LC: QA76.642.P32.
Barbara Chapman, Gabriele Jost, Ruud vanderPas, David Kuck,
Using OpenMP: Portable Shared Memory Parallel Processing,
MIT Press, 2007,
ISBN13: 978-0262533027,
LC: QA76.642.C49.

Source Code:

fft_serial.m, the source code.

Examples and Tests:

fft_serial_output.txt, the output file.

You can go up one level to the MATLAB source codes.