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:
NIterationsTimeTime/CallMegaFLOPS
210,000 1.1325.6e-050.176
410,000 2.2641.1e-040.353
810,000 3.4581.7e-040.693
1610,000 6.0643.0e-041.055
32 1,000 1.0665.3e-041.499
64 1,000 2.3261.1e-031.650
128 1,000 5.1222.5e-031.749
256 1,00011.9595.9e-031.712
512 100 2.9321.4e-021.571
1024 10019.6979.8e-020.519

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

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:

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

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

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

Reference:

  1. 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.
  2. 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.
  3. 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:

Examples and Tests:

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


Last revised on 16 May 2009.